text:
# Linear matrix inequality

(Difference between revisions)
 Revision as of 03:51, 9 November 2007 (edit) (→Convexity of the LMI constraint)← Previous diff Revision as of 01:40, 24 October 2008 (edit) (undo)Next diff → Line 66: Line 66: $\textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}$ $\textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}$ - meaning, the cone interior is nonempty; implying, the dual cone is pointed (Dattorro, ch.2). + meaning, the cone interior is nonempty; implying, the dual cone is pointed ([http://meboo.convexoptimization.com/BOOK/convexgeometry.pdf Dattorro, ch.2]). If matrix $\,A\,$ has no nullspace, on the other hand, then If matrix $\,A\,$ has no nullspace, on the other hand, then

## Revision as of 01:40, 24 October 2008

In convex optimization, a linear matrix inequality (LMI) is an expression of the form

$LaTeX: LMI(y):=A_0+y_1A_1+y_2A_2+\dots+y_m A_m\succeq0\,$

where

• $LaTeX: y=[y_i\,,~i\!=\!1\dots m]$ is a real vector,
• $LaTeX: A_0\,, A_1\,, A_2\,,\dots\,A_m$ are symmetric matrices in the subspace of $LaTeX: n\times n$ symmetric matrices $LaTeX: \mathbb{S}^n$,
• $LaTeX: B\succeq0$ is a generalized inequality meaning $LaTeX: B$ is a positive semidefinite matrix belonging to the positive semidefinite cone $LaTeX: \mathbb{S}_+$ in the subspace of symmetric matrices $LaTeX: \mathbb{S}$.

This linear matrix inequality specifies a convex constraint on y.

## Convexity of the LMI constraint

$LaTeX: LMI(y)\succeq 0$ is a convex constraint on y which means membership to a dual (convex) cone as we now explain: (Dattorro, Example 2.13.5.1.1)

Consider a peculiar vertex-description for a closed convex cone defined over the positive semidefinite cone

(instead of the more common nonnegative orthant, $LaTeX: x\succeq0$):

for $LaTeX: X\!\in\mathbb{S}^n$ given $LaTeX: \,A_j\!\in\mathbb{S}^n$, $LaTeX: \,j\!=\!1\ldots m$

$LaTeX: \begin{array}{ll}\mathcal{K} \!\!&=\left\{\left[\begin{array}{c}\langle A_1\,,\,X^{}\rangle\\\vdots\\\langle A_m\;,\,X^{}\rangle\end{array}\right]|~X\!\succeq_{\!}0\right\}\subseteq_{}\reals^m\\\\ &=\left\{\left[\begin{array}{c}\textrm{svec}(A_1)^T\\\vdots\\\textrm{svec}(A_m)^T\end{array}\right]\!\textrm{svec}X~|~X\!\succeq_{\!}0\right\}\\\\ &:=\;\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0_{}\} \end{array}$

where

• $LaTeX: A\!\in_{}\!\mathbb{R}^{m\times n(n+1)/2}$,
• symmetric vectorization svec is a stacking of columns defined in (Dattorro, Ch.2.2.2.1),
• $LaTeX: A_0=\mathbf{0}$ is assumed without loss of generality.

$LaTeX: \mathcal{K}$ is a convex cone because

$LaTeX: A\,\textrm{svec}{X_{{\rm p}_1}}_{\,},_{_{}}A\,\textrm{svec}{X_{{\rm p}_2}}\!\in\mathcal{K}~\Rightarrow~ A(\zeta_{\,}\textrm{svec}{X_{{\rm p}_1\!}}+_{}\xi_{\,}\textrm{svec}{X_{{\rm p}_2}})\in_{}\mathcal{K} \textrm{~~for\,all~\,}\zeta_{\,},\xi\geq0$

since a nonnegatively weighted sum of positive semidefinite matrices must be positive semidefinite.

Now consider the (closed convex) dual cone:

$LaTeX: \begin{array}{rl}\mathcal{K}^* \!\!\!&=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z\!\in_{_{}\!}\mathcal{K}_{}\right\}\subseteq_{}\reals^m\\ &=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z_{\!}=_{\!}A\,\textrm{svec}X\,,~X\succeq0_{}\right\}\\ &=_{}\left\{_{}y~|~\langle A\,\textrm{svec}X\,,~y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,X\!\succeq_{_{}\!}0_{}\right\}\\ &=\left\{y~|~\langle\textrm{svec}X\,,\,A^{T\!}y\rangle\geq_{}0\;~\textrm{for\,all}~\,X\!\succeq_{\!}0\right\}\\ &=\left\{y~|~\textrm{svec}^{-1}(A^{T\!}y)\succeq_{}0\right\} \end{array}$

that follows from Fejer's dual generalized inequalities for the positive semidefinite cone:

• $LaTeX: Y\succeq0~\Leftrightarrow~\langle Y\,,\,X\rangle\geq0\;~\textrm{for\,all}~\,X\succeq0$

This leads directly to an equally peculiar halfspace-description

$LaTeX: \mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succeq_{}0_{}\}$

The summation inequality with respect to the positive semidefinite cone is known as a linear matrix inequality.

## LMI Geometry

Although matrix $LaTeX: \,A\,$ is finite-dimensional, $LaTeX: \mathcal{K}$ is generally not a polyhedral cone (unless $LaTeX: \,m\,$ equals 1 or 2) simply because $LaTeX: \,X\!\in\mathbb{S}_+^n\,$.

Provided the $LaTeX: A_j$ matrices are linearly independent, then relative interior = interior

$LaTeX: \textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}$

meaning, the cone interior is nonempty; implying, the dual cone is pointed (Dattorro, ch.2).

If matrix $LaTeX: \,A\,$ has no nullspace, on the other hand, then $LaTeX: \,A\,\textrm{svec}X\,$ is an isomorphism in $LaTeX: \,X\,$ between the positive semidefinite cone $LaTeX: \mathbb{S}_+^n$ and range $LaTeX: \,\mathcal{R}(A)\,$ of matrix $LaTeX: \,A$.

In that case, convex cone $LaTeX: \,\mathcal{K}\,$ has relative interior

$LaTeX: \textrm{rel\,int}\mathcal{K}=\{A\,\textrm{svec}X~|~X\!\succ_{\!}0_{}\}$

and boundary

$LaTeX: \textrm{rel}\,\partial^{}\mathcal{K}=\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0\,,~X\!\nsucc_{\!}0_{}\}$

When the $LaTeX: A_j$ matrices are linearly independent, function $LaTeX: \,g(y)_{\!}:=_{_{}\!}\sum y_jA_j\,$ on $LaTeX: \mathbb{R}^m$ is a linear bijection.

Inverse image of the positive semidefinite cone under $LaTeX: \,g(y)\,$ must therefore have dimension $LaTeX: _{}m$.

In that circumstance, the dual cone interior is nonempty

$LaTeX: \textrm{int}\mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succ_{}0_{}\}$

having boundary

$LaTeX: \partial^{}\mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succeq_{}0\,,~\sum\limits_{j=1}^my_jA_j\nsucc_{}0_{}\}$

## Applications

There are efficient numerical methods to determine whether an LMI is feasible (i.e., whether there exists a vector $LaTeX: y$ such that $LaTeX: LMI(y)\succeq0$ ), or to solve a convex optimization problem with LMI constraints. Many optimization problems in control theory, system identification, and signal processing can be formulated using LMIs. The prototypical primal and dual semidefinite program is a minimization of a real linear function respectively subject to the primal and dual convex cones governing this LMI.


text:
# reduce space before and after verse environment

I want to reduce globally in a document the vertical space before and after a verse environment. The MWE shows the problem, with output:

I would like not to use other packages, because I want to learn some low-level commands. I know that verse is based on a list environment. A related answer (How to eliminate vertical space before and after verse environment?) seems overly complex, and uses the verse package (not the built-in version). Surely there is a way to

\setlength{\versesep}{0pt}

or something like it?

Or (since I am using xpatch package anyway), could I do something like

\xpatchcmd\verse{\...

But I don't know how to find the original code for the verse environment, and so I don't know which line to modify.

\documentclass[12pt,oneside]{article}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1em}

\begin{document}

This is a paragraph.

This is another paragraph.  Separated nicely.

\begin{verse}
This is some\\
lovely verse,\\
that has too much space\\
on top and below.
\end{verse}

I would really like not as much space above and below.  Just one parskip would be sufficient.

But other paragraphs should be spaced with parskip.

\end{document}
• Remove \setlength{\parskip}{1em} (that doesn't make much sense anyway). – egreg Dec 22 '15 at 10:46
• This will affect the normal paragraphs, which I don't want to do. I just edited the question to clarify this. – Tim Dec 22 '15 at 10:54

Remove the added \parskip by reducing \topsep:

\documentclass[12pt,oneside]{article}
\usepackage{xpatch}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1em}

\begin{document}

This is a paragraph.

\begin{verse}
This is some\\
lovely verse,\\
that has too much space\\
on top and below.
\end{verse}

I would really like not as much space above and below.  Just one parskip would be sufficient

I would really like not as much space above and below.  Just one parskip would be sufficient

\end{document}

• I compiled your solution inside my real document (two columned, landscape) and the vertical space still looked too big, until I added 'ragged bottom', which fixed things. Can you add to your answer please how to limit the stretchiness inside the \verse command so that I do not need the \raggedbottom? – Tim Dec 22 '15 at 12:21
• @Tim Two column and raggedbottom don't go along; in this case you are responsible of setting the spacing parameters so that columns are filled up correctly. Possibly adding a bit of stretching or shrinking to such a gigantic \parskip can help. – egreg Dec 22 '15 at 12:52

Without other packages, maybe something like this:

\documentclass[12pt,oneside]{article}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1em}

\let\oldverse\verse
\renewenvironment{verse}{%
\vspace{-\parskip}
\oldverse
}

\begin{document}

This is a paragraph.

This is another paragraph.  Separated nicely.

\begin{verse}
This is some\\
lovely verse,\\
that has too much space\\
on top and below.
\end{verse}

I would really like not as much space above and below.  Just one parskip would be sufficient.

But other paragraphs should be spaced with parskip.

\end{document}

format: plain


text:
5

# (a) How would the man whose case is described in the Appendix score on Eysenck's supertraits? (b) How would he score on the Big Five traits?(c) How would you s...

## Question

###### (a) How would the man whose case is described in the Appendix score on Eysenck's supertraits? (b) How would he score on the Big Five traits?(c) How would you score on Eysenck's traits and the Big Five traits? (Remember that all traits are continuous.)

(a) How would the man whose case is described in the Appendix score on Eysenck's supertraits? (b) How would he score on the Big Five traits? (c) How would you score on Eysenck's traits and the Big Five traits? (Remember that all traits are continuous.)

#### Similar Solved Questions

##### Example3: Evaluate | tan xsec X dx
Example3: Evaluate | tan xsec X dx...
##### OK, this is the last time for one of these crazy adventures. THIS time, though, there window in the" Iloor; and you can see that you re in _ rocket which has just taken off from the surface of an alien planet. By taking careful measurements out that window you determine that the rocket is accelerating upward at 5.59 mVs^2. When you drop ball from height of 1.37 m, hits the floor 0.351 later: What the value of tor the alien world below you?
OK, this is the last time for one of these crazy adventures. THIS time, though, there window in the" Iloor; and you can see that you re in _ rocket which has just taken off from the surface of an alien planet. By taking careful measurements out that window you determine that the rocket is accel...
##### Calculate E? AG' and Kc for the voltaic pts:) cell composed by following half cel(Cu?*(aq) 2e + Cuish E? = +0.34V; Brzm 2e" 28ri9h E? = +1.O7V)Identily name thost fve fdnterena| foctiona} groups within the following molecule. Circle funcllona groups (5 pts): and HOUse the following table to calculate 4S" for the reaction (5 pls) SiCllg) 2Mg(s) 2MgCh(s) Si(s) Substance: SiCl(g) Mg(s) Mgck(e) Sils) S"(JIK mol): 330.73 32.68 89.62 18.83
Calculate E? AG' and Kc for the voltaic pts:) cell composed by following half cel (Cu?*(aq) 2e + Cuish E? = +0.34V; Brzm 2e" 28ri9h E? = +1.O7V) Identily name thost fve fdnterena| foctiona} groups within the following molecule. Circle funcllona groups (5 pts): and HO Use the following tab...
##### Note: Use radians when evaluating the trigonometric functionsProblem&i Starting with the initial guesses of x = and V = 1, solve for xand y in the following system of nonlinear equations by applying one iteration of the Newton-Raphson method. Show your work_ and put a box around your values of x and y at the end of the first iteration. [25 points] sin(3x) + Sxy2 = 8 x2y3 + 7e-2y 2e
Note: Use radians when evaluating the trigonometric functions Problem&i Starting with the initial guesses of x = and V = 1, solve for xand y in the following system of nonlinear equations by applying one iteration of the Newton-Raphson method. Show your work_ and put a box around your values of ...
##### Q2merks) A 0.5 kJ Frojectle Is Iaunchcd = Jan unknown angle betore hitna the glound above torizon Irorn 3 poitt Wnai [5 tne , J0 m Iall buadlng (patnt A) cange {cacics 10 m1 abovc 0s Kneuc cnergy from lnuhching point = Poinn haunching poent 107 hlts the ground ( KR KaJ? TakeSulud &teCanota dritted15J20 .
Q2merks) A 0.5 kJ Frojectle Is Iaunchcd = Jan unknown angle betore hitna the glound above torizon Irorn 3 poitt Wnai [5 tne , J0 m Iall buadlng (patnt A) cange {cacics 10 m1 abovc 0s Kneuc cnergy from lnuhching point = Poinn haunching poent 107 hlts the ground ( KR KaJ? Take Sulud &te Canota d...
##### Use the meaning of the symbols $\in$ and $\notin$ to determine whether each statement is true or false. $\sqrt{2} \notin\{x \mid x$ is a rational number
Use the meaning of the symbols $\in$ and $\notin$ to determine whether each statement is true or false. $\sqrt{2} \notin\{x \mid x$ is a rational number...
##### Alck deposited S1000 into hls saving account every month for 10 years: How much moncy does Rick have his account at the endof 10 years, If the money earns Interest ata rate of 12% per annum compounded monthly? [5]Paul can invest his SSO 0OO lottery winnings in two wavs: Method 8% per annum compounded quarterly for 10 years Method 12% per annum for = years What the difference between the interest earned on the two investments? Which investment should Paul invest his money in? Explain why: [10]
Alck deposited S1000 into hls saving account every month for 10 years: How much moncy does Rick have his account at the endof 10 years, If the money earns Interest ata rate of 12% per annum compounded monthly? [5] Paul can invest his SSO 0OO lottery winnings in two wavs: Method 8% per annum compound...
##### For the following exercises, find the inverse of the functions.$$f(x)= rac{x-2}{x+7}$$
For the following exercises, find the inverse of the functions. $$f(x)=\frac{x-2}{x+7}$$...
##### For a one-tailed (upper tail) hypothesis test with a sample size of 26 and a .01 level of significance, the critical value of the test statistic t is2.797.2.787.2.485.2.479.
For a one-tailed (upper tail) hypothesis test with a sample size of 26 and a .01 level of significance, the critical value of the test statistic t is 2.797. 2.787. 2.485. 2.479....
##### Graph the inequality.$$6 y<24$$
Graph the inequality. $$6 y<24$$...
##### Write the expression as the sine, cosine, or tangent of a doubleangle. Then find the exact value of the expression.2 sin 75Â° cos 75Â°
Write the expression as the sine, cosine, or tangent of a double angle. Then find the exact value of the expression. 2 sin 75Â° cos 75Â°...
##### Let $a>0$ and $n>1 .$ Define $f(x)=\frac{x^{n}}{e^{a x}-1}$ for $x \neq 0$ and $f(0)=0$ (a) Use L'Hópital's Rule to show that $f(x)$ is continuous at $x=0$ (b) Show that $\int_{0}^{\infty} f(x) d x$ converges. Hint: Show that $f(x) \leq$ 2$x^{n} e^{-a x}$ if $x$ is large enough. Then use the Comparison Test and Exercise $91 .$
Let $a>0$ and $n>1 .$ Define $f(x)=\frac{x^{n}}{e^{a x}-1}$ for $x \neq 0$ and $f(0)=0$ (a) Use L'Hópital's Rule to show that $f(x)$ is continuous at $x=0$ (b) Show that $\int_{0}^{\infty} f(x) d x$ converges. Hint: Show that $f(x) \leq$ 2$x^{n} e^{-a x}$ if $x$ is large enough. ...
##### -/1 pointsSerCP11 7.A.P.047.My NotesAsk Your Teacher(a) One of the moons of Jupiter; named [0, has an orbital radius of 4.22 x 108 m and period of 1.77 days. Assuming the orbit is circular; calculate the mass of Jupiter: kg(b) The largest moon of Jupiter; named Ganymede, has an orbital radius of 1,07 109 m and period of 7.16 days. Calculate the mass of Jupiter from this data_ kg(c) Are your results to parts (a) and (b) consistent? Yes No
-/1 points SerCP11 7.A.P.047. My Notes Ask Your Teacher (a) One of the moons of Jupiter; named [0, has an orbital radius of 4.22 x 108 m and period of 1.77 days. Assuming the orbit is circular; calculate the mass of Jupiter: kg (b) The largest moon of Jupiter; named Ganymede, has an orbital radius o...
##### 1. A large storage tank, open at the top and filled withwater, develops a small hole in its side at apoint 16.8 m below the water level. The rate of flow fromthe leak is found to be 2.00 10-3m3/min.(a) Determine the diameter of the hole.2. The gravitational force exerted on a solid objectis 5.50 N. When the object is suspended from a springscale and submerged in water, the scale reads 3.50 N asshown in the figure below. Find the density of the object.
1. A large storage tank, open at the top and filled with water, develops a small hole in its side at a point 16.8 m below the water level. The rate of flow from the leak is found to be 2.00 10-3m3/min. (a) Determine the diameter of the hole. 2. The gravitational force exerted on a solid object is 5...
##### 02 A) The numbcr of hours worked by 10 employecs of small building firm during ucck of work #ef6:45 4} Calculate thc: median; mode; mean and slandard deviation of the hours worked by thc cmployccs.
02 A) The numbcr of hours worked by 10 employecs of small building firm during ucck of work #ef6:45 4} Calculate thc: median; mode; mean and slandard deviation of the hours worked by thc cmployccs....


text:
Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1061.34053
Lu, Shiping; Ge, Weigao
Existence of positive periodic solutions for neutral logarithmic population model with multiple delays.
(English)
[J] J. Comput. Appl. Math. 166, No. 2, 371-383 (2004). ISSN 0377-0427

The authors study the existence of positive periodic solutions for a neutral delay logarithmic population model with multiple delays of the form $${dN\over dt}= N(t)\Biggl[r(t)- \sum^N_{j=1} a_i(t)\ln N(t- \sigma_i(t))- \sum^m_{j=1} b_j(t){d\over dt}\ln N(t-\tau_j(t))\Biggr],\tag1$$ with $\sigma_j(t)\ge 0$ and $\tau_j(t)\ge 0$. The goal of this paper is to establish some criteria guaranteeing the existence of positive periodic solutions of (1). Under some suitable assumptions on the data of (1), the authors obtain a new existence result by using an abstract continuation theorem for $k$-set contraction and some other analytic techniques.
[Messoud A. Efendiev (Berlin)]
MSC 2000:
*34K13 Periodic solutions of functional differential equations
35K40 Systems of parabolic equations, general
34K60 Applications of functional-differential equations
92D25 Population dynamics

Keywords: neutral delay logarithmic population model; $k$-set contractive operator; positive periodic solution

Highlights
Master Server


text:
homechevron_rightStudychevron_rightMathchevron_rightAlgebra

# Determinant of 3x3 matrices

This calculator calculates the determinant of 3x3 matrices

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/157/. Also, please do not modify any references to the original work (if any) contained in this content.

The determinant is a value defined for a square matrix. It is important when matrix is used to solve system of linear equations (for example Solution of a system of 3 linear equations).

The determinant of 3x3 matrix is defined as
$\left|\begin{matrix} a & b & c \\ d & e & f \\ g & h & i \end{matrix} \right| = aei - afh - bdi + bfg + cdh - ceg$

#### Determinant of 3x3 matrices

Digits after the decimal point: 2
Determinant

URL copied to clipboard
PLANETCALC, Determinant of 3x3 matrices


text:
# Can't write data in for 24c256 eeprom?

I am using Pic24fj128ga202 microcontroller and 24c256 eeprom and ISL1208 RTC which is interfaced through I2c bus. The problem is i can able to read and write the data in eeprom and RTC ,but on some other boards (with same design ) i can't read or write the data through i2c bus. I have posted my code and schematic also kindly anyone address me what is the problem? I don't have oscilloscope to check this.

#include <stdio.h>
#include "C:\Program Files\Microchip\xc16\v1.24\support\PIC24F\h\p24FJ128GA202.h"
#include "uart.h"
// calculate baud rate of I2C
#define Fosc      32000000
#define Fcy       (Fosc/2)
#define Fsck      400000
#define I2C_BRG  ((Fcy/2/Fsck)-1)

int main()
{
InitProcessor();
Delayms();
while(1)
{
I2c_Write(0xA0,1,'A');
Delayms(5000);
}
}

void InitProcessor(void)
{
// Oscillator    8mhz no pll
OSCCON = 0x0011;
CLKDIV = 0x0000;

// Configure Digital pins
ANSA = 0x0003;
ANSB = 0x0000;

//  Assign  IO values for Ports
PORTA = 0x0000;
TRISA = 0x001B;
TRISB = 0x468f;                   // 7 as receive and 8 as transmitter
//PORTB = 0x0000;

// Interrupt Bits
INTCON1 = 0x0000;                                               // Disable  Interrupts
INTCON2 = 0x0000;

// Init I2C
I2C2CONL = 0x8000;
I2C2CONH = 0x0000;
I2C2STAT = 0x0000;
I2C2BRG = I2C_BRG;
//I2C2BRG = 79;

Delayms(1000);
Init_rtc();
}

void Init_rtc()
{
I2c_Write(0xde, 0x07, 0x10);
I2c_Write(0xde, 0x06, 0x00);
Delayms(20);
}

{
unsigned char i2c_exit=1,i2c_write=0;
int I2creg = 0;
IFS3 &= ~0x0004;
I2C2CONL |= 0x0001;
I2cTimer = 0;
while(i2c_exit)
{
if(I2cTimer > 30){                                              // Exit routine
i2c_exit = 0;
}
if(IFS3& 0x0004)
{
IFS3 &= ~0x0004;
I2cTimer = 0;
if(i2c_write == 0)
{
i2c_write = 1;
}
else if(i2c_write == 1)
else if(i2c_write == 2)
else if(i2c_write == 3)
I2C2TRN = i2c_value;
else if(i2c_write == 4)
I2C2CONL |= 0x04;
else
{
i2c_write = 100;
i2c_exit = 0;
}
i2c_write++;
}
}
Delayms(5);
}

/* Function to Read and return a data through I2C  */
IFS3 &= ~0x0004;                                                        // Master I2C interrupt flag
I2CFlag = 1;
I2C2CONL |= 0x0001;         // SEN = 1;
I2cTimer = 0;
while(I2CFlag){
if(I2cTimer > 30){                                              // Exit routine
I2CFlag = 0;

//ModemDiagnostics(64,1);
}
//uart1tx('r');
if(IFS3 & 0x0004)
{
I2cTimer = 0;
IFS3 &= ~0x0004;
{
}
else if(ReadState == 3)I2C2CONL |= 0x0002;
I2C2CONL |= 0x0008;                             // RCEN = 1, Enable data receive
db = I2C2RCV;
}
db = I2C2RCV;                                                       // Read Data
I2C2CONL |= 0x0020;                                                 // ACKDT = 1, Set Acknowledge bit (No Acknowledge)
Delayms(5);
I2C2CONL |= 0x0010;                                                 // ACKEN = 1
}
else if(ReadState == 7)I2C2CONL |= 0x04;                                // PEN = 1, Stop enable bit forI2C
else{ReadState = 100; I2CFlag = 0;}
}
}
if(db)
return db;
else
return 0;
}

• Without digging too much, I suspect that the pullup resistors (R41 and R42) are too high a value (the total capacitance of the circuit is something I cannot know). Try replacing them with 4.7k or perhaps 2.2k – Peter Smith Aug 19 '16 at 10:47

The calculation of the maximum pull-up at 400kHz is:

$R_{max}$ = $\frac {300ns} {C_{bus}}$; rearranging, we get:

$C_{bus(max)}$ = $\frac {300ns} {10k\Omega}$ for your case, yielding 30pF.

The pin capacitances of the EEPROM and RTC are both probably of the order of 10pF; add the pin capacitance of the PIC and you are approaching 30pF already, putting the design on a hairy edge (to use the common term), where it may or may not operate properly, which is precisely what you are experiencing.

It is not difficult to get 10pF or more of stray capacitance, and this would violate the requirement for the maximum pull-up size, leading to corrupted I2C data.

If you replace these parts with 4.7k, you are allowed almost 64pF of bus capacitance which will very likely solve the issue.

As noted, if you reduce the bus speed and it operates properly, that is a clear indicator this is the issue.

• thank you @ Peter smith .i am looking forward to address the issue.. and sometimes micro-controller restarts is there any problem by this? – Pradeep kumark Aug 20 '16 at 6:18
• Whether the controller restarts depends on many things, including whether unhandled communication failures have some side effect. I have not read the details of the controller. – Peter Smith Aug 20 '16 at 17:27

Because it is working as you want in another board, I will assume the problems comes from the hardware (even if a bad software can make it worse). I can see 2 reasons for this:

• One of the pins of your IC is not properly connected. Do continuity tests with a multimeter between pins of different ICs to check they are properly connected together
• For some reason, one of your electrical parameter is out of the limits of the Datasheets. This may lead some boards to work, whereas others would not.
• +1 As well as opens, shorts are also a possibility – Spehro Pefhany Aug 19 '16 at 12:55


text:
# Getting fast performance from a STM32 MCU

I am working with the STM32F303VC discovery kit and I am slightly puzzled by its performance. To get acquainted with the system, I've written a very simple program simply to test out the bit-banging speed of this MCU. The code can be broken down as follows:

1. HSI clock (8 MHz) is turned on;
2. PLL is initiated with the with the prescaler of 16 to achieve HSI / 2 * 16 = 64 MHz;
3. PLL is designated as the SYSCLK;
4. SYSCLK is monitored on the MCO pin (PA8), and one of the pins (PE10) is constantly toggled in the infinite loop.

The source code for this program is presented below:

#include "stm32f3xx.h"

int main(void)
{
// Initialize the HSI:
RCC->CR |= RCC_CR_HSION;
while(!(RCC->CR&RCC_CR_HSIRDY));

// Initialize the LSI:
// RCC->CSR |= RCC_CSR_LSION;
// while(!(RCC->CSR & RCC_CSR_LSIRDY));

// PLL configuration:
RCC->CFGR &= ~RCC_CFGR_PLLSRC;     // HSI / 2 selected as the PLL input clock.
RCC->CFGR |= RCC_CFGR_PLLMUL16;   // HSI / 2 * 16 = 64 MHz
RCC->CR |= RCC_CR_PLLON;          // Enable PLL
while(!(RCC->CR&RCC_CR_PLLRDY));  // Wait until PLL is ready

// Flash configuration:
FLASH->ACR |= FLASH_ACR_PRFTBE;
FLASH->ACR |= FLASH_ACR_LATENCY_1;

// Main clock output (MCO):
RCC->AHBENR |= RCC_AHBENR_GPIOAEN;
GPIOA->MODER |= GPIO_MODER_MODER8_1;
GPIOA->OTYPER &= ~GPIO_OTYPER_OT_8;
GPIOA->PUPDR &= ~GPIO_PUPDR_PUPDR8;
GPIOA->OSPEEDR |= GPIO_OSPEEDER_OSPEEDR8;
GPIOA->AFR[0] &= ~GPIO_AFRL_AFRL0;

// Output on the MCO pin:
//RCC->CFGR |= RCC_CFGR_MCO_HSI;
//RCC->CFGR |= RCC_CFGR_MCO_LSI;
//RCC->CFGR |= RCC_CFGR_MCO_PLL;
RCC->CFGR |= RCC_CFGR_MCO_SYSCLK;

// PLL as the system clock
RCC->CFGR &= ~RCC_CFGR_SW;    // Clear the SW bits
RCC->CFGR |= RCC_CFGR_SW_PLL; //Select PLL as the system clock
while ((RCC->CFGR & RCC_CFGR_SWS_PLL) != RCC_CFGR_SWS_PLL); //Wait until PLL is used

// Bit-bang monitoring:
RCC->AHBENR |= RCC_AHBENR_GPIOEEN;
GPIOE->MODER |= GPIO_MODER_MODER10_0;
GPIOE->OTYPER &= ~GPIO_OTYPER_OT_10;
GPIOE->PUPDR &= ~GPIO_PUPDR_PUPDR10;
GPIOE->OSPEEDR |= GPIO_OSPEEDER_OSPEEDR10;

while(1)
{
GPIOE->BSRRL |= GPIO_BSRR_BS_10;
GPIOE->BRR |= GPIO_BRR_BR_10;

}
}

The code was compiled with CoIDE V2 with the GNU ARM Embedded Toolchain using -O1 optimization. The signals on pins PA8 (MCO) and PE10, examined with an oscilloscope, look like this:

The SYSCLK appears to be configured correctly, as the MCO (orange curve) exhibits an oscillation of nearly 64 MHz (considering the error margin of the internal clock). The weird part for me is the behavior on PE10 (blue curve). In the infinite while(1) loop it takes 4 + 4 + 5 = 13 clock cycles to perform an elementary 3-step operation (i.e. bit-set/bit-reset/return). It gets even worse on other optimization levels (e.g. -O2, -O3, ar -Os): several additional clock cycles are added to the LOW part of the signal, i.e. between the falling and rising edges of PE10 (enabling the LSI somehow seems to remedy this situation).

Is this behavior expected from this MCU? I would imagine a task as simple as setting and resetting a bit ought to be 2-4 times faster. Is there a way to speed things up?

• Have you tried with some other MCU to compare? – Marko Buršič Mar 28 '17 at 8:35
• What re you trying to achieve? If you want a fast oscillating output you should be using timers. If you want to interface with fast serial protocols, you should be using the corresponding hardware peripherial. – Jonas Schäfer Mar 28 '17 at 11:41
• Great start with the kit!! – Scott Seidman Mar 28 '17 at 12:41
• You must not |= BSRR or BRR registers as they are write only. – 0___________ Apr 15 '18 at 11:22

The question here really is: what is the machine code you're generating from the C program, and how does it differ from what you'd expect.

If you didn't have access to the original code, this would've been an exercise in reverse engineering (basically something starting with: radare2 -A arm image.bin; aaa; VV), but you've got the code so this makes it all easier.

First, compile it with the -g flag added to the CFLAGS (same place where you also specify -O1). Then, look at the generated assembly:

arm-none-eabi-objdump -S yourprog.elf

Notice that of course both the name of the objdump binary as well as your intermediate ELF file might be different.

Usually, you can also just skip the part where GCC invokes the assembler and just look at the assembly file. Just add -S to the GCC command line – but that will normally break your build, so you'd most probably do it outside your IDE.

arm-none-eabi-gcc
-S  ## stop after generating assembly, i.e. don't run as
-I/path/to/CMSIS/ST/STM32F3xx/ -I/path/to/CMSIS/include
test.c

and got the following (excerpt, full code under link above):

.L5:
ldr r2, [r3, #24]
orr r2, r2, #1024
str r2, [r3, #24]
ldr r2, [r3, #40]
orr r2, r2, #1024
str r2, [r3, #40]
b   .L5

Which is a loop (notice the unconditional jump to .L5 at the end and the .L5 label at the beginning).

What we see here is that we

• first ldr (load register) the register r2 with the value at memory location stored in r3+ 24 Bytes. Being too lazy to look that up: very likely the location of BSRR.
• Then OR the r2 register with the constant 1024 == (1<<10), which would correspond to setting the 10th bit in that register, and write the result to r2 itself.
• Then str (store) the result in the memory location we've read from in the first step
• and then repeat the same for a different memory location, out of lazyness: most likely BRR's address.
• Finally b (branch) back to the first step.

So we have 7 instructions, not three, to start with. Only the b happens once, and thus is very likely what's taking an odd number of cycles (we have 13 in total, so somewhere an odd cycle count must come from). Since all odd numbers below 13 are 1, 3, 5, 7, 9, 11, and we can rule out any numbers larger than 13-6 (assuming the CPU can't execute an instruction in less than one cycle), we know that the b takes 1, 3, 5, or 7 CPU cycles.

Being who we are, I looked at ARM's documentation of instructions and how much cycles they take for the M3:

• ldr takes 2 cycles (in most cases)
• orr takes 1 cycle
• str takes 2 cycles
• b takes 2 to 4 cycles. We know it must be an odd number, so it must take 3, here.

That all lines up with your observation:

\begin{align} 13 &= 2\cdot(&c_\mathtt{ldr}&+c_\mathtt{orr}&+c_\mathtt{str})&+c_\mathtt{b}\\ &= 2\cdot(&2&+1&+2)&+3\\ &= 2\cdot &5 &&&+3 \end{align}

As the above calculation shows, there will hardly be a way of making your loop any faster – the output pins on ARM processors are usually memory mapped, not CPU core registers, so you have to go through the usual load – modify – store routine if you want to do anything with those.

What you could of course do is not read (|= implicitly has to read) the pin's value every loop iteration, but just write the value of a local variable to it, which you just toggle every loop iteration.

Notice that I feel like you might be familiar with 8bit micros, and would be attempting to read only 8 bit values, store them in local 8 bit variables, and write them in 8 bit chunks. Don't. ARM is a 32bit architecture, and extracting 8 bit of a 32bit word might take additional instructions. If you can, just read the whole 32bit word, modify what you need, and write it back as whole. Whether that is possible of course depends on what you're writing to, i.e. the layout and functionality of your memory-mapped GPIO. Consult the STM32F3 datasheet/user's guide for info on what is stored in the 32bit containing the bit you want to toggle.

Now, I tried to reproduce your issue with the "low" period getting longer, but I simply couldn't – the loop looks exactly the same with -O3 as with -O1 with my compiler version. You'll have to do that yourself! Maybe you're using some ancient version of GCC with suboptimal ARM support.

• Wouldn't just storing (= instead of |=), as you say, be exactly the speedup the OP is looking for? The reason ARMs have the BRR and BSRR registers separately is to not require read-modify-write. In this case, the constants could be stored in registers outside the loop, so the inner loop would be just 2 str's and a branch, so 2 + 2 +3 = 7 cycles for the whole round? – Timo Mar 28 '17 at 10:31
• Thanks. That really cleared things up quite a bit. It was a bit of hasty thinking to insist that only 3 clock cycles would be needed - 6 to 7 cycles were something that I was actually hoping for. The -O3 error seems to have disappeared after cleaning and rebuilding the solution. Nonetheless, my assembly code seems to have an additional UTXH instruction within it: .L5: ldrh r3, [r2, #24] uxth r3, r3 orr r3, r3, #1024 strh r3, [r2, #24] @ movhi ldr r3, [r2, #40] orr r3, r3, #1024 str r3, [r2, #40] b .L5 – K.R. Mar 28 '17 at 10:36
• uxth is there because GPIO->BSRRL is (incorrectly) defined as a 16 bit register in your headers. Use a recent version of the headers, from the STM32CubeF3 libraries, where there is no BSRRL and BSRRH, but a single 32 bit BSRR register. @Marcus apparently has the correct headers, so his code does full 32 bit accesses instead of loading a halfword and extending it. – followed Monica to Codidact Mar 28 '17 at 10:46
• Why would loading a single byte take extra instructions? The ARM architecture has LDRB and STRB that perform byte reads/write in a single instruction, no? – psmears Mar 28 '17 at 11:12
• The M3 core can support bit-banding (not sure if this particular implementation does), where a 1 MB region of peripheral memory space is aliased to a 32 MB region. Each bit has a discrete word address (bit 0 is used only). Presumably still slower than just a load/store. – Sean Houlihane Mar 29 '17 at 15:20

The BSRR and BRR registers are for setting and resetting individual port bits:

GPIO port bit set/reset register (GPIOx_BSRR)

...

(x = A..H) Bits 15:0

BSy: Port x set bit y (y= 0..15)

These bits are write-only. A read to these bits returns the value 0x0000.

0: No action on the corresponding ODRx bit

1: Sets the corresponding ODRx bit

As you can see, reading these registers always gives 0, therefore what your code

GPIOE->BSRRL |= GPIO_BSRR_BS_10;
GPIOE->BRR |= GPIO_BRR_BR_10;

does effectively is GPIOE->BRR = 0 | GPIO_BRR_BR_10, but the optimizer doesn't know that, so it generates a sequence of LDR, ORR, STR instructions instead of a single store.

You can avoid the expensive read-modify-write operation by simply writing

GPIOE->BSRRL = GPIO_BSRR_BS_10;
GPIOE->BRR = GPIO_BRR_BR_10;

You might get some further improvement by aligning the loop to an adress evenly divisible by 8. Try putting one or mode asm("nop"); instructions before the while(1) loop.

To add to what has been said here: Certainly with the Cortex-M, but pretty much any processor (with a pipeline, cache, branch prediction or other features), it is trivial to take even the simplest loop:

top:
subs r0,#1
bne top

Run it as many millions of times as you want, but be able to have the performance of that loop vary widely, just those two instructions, add some nops in the middle if you like; it doesn't matter.

Changing the alignment of the loop can vary the performance dramatically, especially with a small loop like that if it takes two fetch lines instead of one, you eat that extra cost, on a microcontroller like this where the flash is slower than the CPU by 2 or 3 and then by upping the clock the ratio gets even worse 3 or 4 or 5 than adding extra fetching.

You likely don't have a cache, but if you had that it helps in some cases, but it hurts in others and/or doesn't make a difference. Branch prediction which you may or may not have here (probably not) can only see as far as designed in the pipe, so even if you changed the loop to branch out and had an unconditional branch at the end (easier for a branch predictor to use) all that does is save you that many clocks (size of the pipe from where it would normally fetch to how deep the predictor can see) on the next fetch and/or it doesn't do a prefetch just in case.

By changing the alignment with respect to fetch and cache lines you can affect whether or not the branch predictor is helping you or not, and that can be seen in the overall performance, even if you are only testing two instructions or those two with some nops.

It is somewhat trivial to do this, and once you understand that, then taking compiled code, or even hand written assembly, you can see that its performance can vary widely due to these factors, adding or saving a few to a couple hundred percent, one line of C code, one poorly placed nop.

After learning to use the BSRR register, try running your code from RAM (copy and jump) instead of flash that should give you an instant 2 to 3 times performance boost in the execution without doing anything else.

Is this behavior expected from this MCU?

It is a behavior of your code.

1. You should write to BRR/BSRR registers, not read-modify-write as you do now.

2. You also incur loop overhead. For maximum performance, replicate the BRR/BSRR operations over and over again → copy-and-paste them in the loop multiple times so you go through many set/reset cycles before one loop overhead.

edit: some quick tests under IAR.

a flip through writing to BRR/BSRR takes 6 instructions under moderate optimization and 3 instructions under highest level of optimization; a flip through RMW'ng takes 10 instructions / 6 instructions.

• By changing |= to = a single bit set/reset phase consumes 9 clock cycles (link). The assembly code is 3 instructions long: .L5 strh r1, [r3, #24] @ movhi str r2, [r3, #40] b .L5 – K.R. Mar 28 '17 at 11:17
• Don't manually unroll loops. That's practically never a good idea. In this particular case, it's especially desastrous: it makes the waveform non-periodic. Also, having the same code many time in flash isn't necessarily faster. This might not apply here (it might!), but loop unrolling is something that many people think helps, that compilers (gcc -funroll-loops) can do very well, and that when abused (like here) has the inverse effect of what you want. – Marcus Müller Mar 28 '17 at 20:45
• @MarcusMüller: Infinite loops can sometimes be usefully unrolled while maintaining consistent timing if there are any points in some repetitions of the loop where an instruction would have no visible effect. For example, if somePortLatch controls a port whose lower 4 bits are set for output, it may be possible to unroll while(1) { SomePortLatch ^= (ctr++); } into code that outputs 15 values and then loops back to start at the time when it would otherwise output the same value twice in a row. – supercat Mar 28 '17 at 23:16


text:
# All Questions

1answer
140 views

### Resources for basics of lattice crypto [closed]

I'm looking to fill in the gaps of my knowledge of lattices. Can anyone point me towards papers or books that introduce lattice crypto assuming a fairly solid math background? Mods: Feel free to ...
1answer
117 views

### Signature with appendix

I see sometimes signatures schemes with appendix. This is about signatures schemes in which the message is needed in the verification algorithm, that is, the ouput of the signature algorithm is of the ...
1answer
88 views

### How to choose the appropriate public (i, m) and private (j, m) keys?

I studied some encryption and decryption and I have found some very interesting problem to solve on the internet. I hope I am writing to right site - there are so many in StackExchange otherwise I ...
1answer
131 views

### Trying to finalize my understanding about password storing

am sorry, an a beginner, so please forgive me if i make mistakes, so here is what I understood: PBKDF2: uses HMAC, so, the message is the password, and the key that crypts the message is the salt? or ...
2answers
603 views

### Reversing SHA1 (don't know the correct term)

Given sha1(pad(A) || pad(B)), where B is known, can I calculate sha1(pad(A))? pad(A) means its length is exactly 1 block (64 bytes for SHA-1) If yes, for which other hash functions it will work too? ...
1answer
131 views

### Size of Parameters in Polynomial Key-Splitting Algorithm

I've seen the elegant way of splitting a key among different people so that only a certain number need to be present to re-compute the key, yet nobody has enough information to re-compute the key on ...
1answer
163 views

### Weak One Way Function

Show The function $mult(a,b)$ is weak one way if the Integer Factorization Assumption is true. I am read the proof of this enunciated but I want know if I understand this in my way. The proof use the ...
1answer
99 views

### reduces the coefficients of a modulo 3 on NTRU

i'm still don't understand about 'reduces the coefficients of a modulo 3' on NTRU tutorial $a = f*e = 3 - 7X - 10X^2 - 11X^3 + 10X^4 + 7X^5 + 6X^6 + 7X^7 + 5X^8 - 3X^9 -7X^{10} \pmod{32}.$ Note ...
1answer
188 views

### Solving congruences using PARI

I'm having trouble finding info in the docs about how to solve a system of congruences. The closest I can find is 'matsolvemod' in here: ...
1answer
244 views

### How to secure a mental poker protocol? [closed]

I would like to implement a mental poker protocol in a secure fashion. How should I go about that without (preferably) infringing on the Mental Poker Framework patent?
1answer
475 views

### Is AES reducible to an NP-complete problem?

Is breaking AES NP-hard? Can the security of AES be reduced to a NP-complete problem? If it is reducible, what does the reduction look like? If it is not reducible, why do we assume it is secure?
2answers
644 views

### Kryptos : K1. What is the origin of the “palimpsest” keyword?

I'm studying the Kryptos sculpture with its cryptographic puzzles K1 to K4. I understand that the keyword "palimpsest" was reverse-engineered using the tableau (and brute-force computer processing), ...
1answer
530 views

### Learning cryptography using a FPGA

I have a FPGA and am curious what cryptographic applications I can use with it. I'm just a hobbyist / security researcher and not a professional cryptographer. Since I'm creating my own curriculum, ...
1answer
253 views

### What is the complexity of the Square attack against the reduced 4-rounds 128-bit Rijndael variant?

I'm looking at a square attack against a reduced version of AES-128 with only 4 rounds (with block and key size of each 128 bit). I have a set of 256 plaintext-ciphertext block pairs. What is the ...
1answer
1k views

### AES encryption for images [closed]

Why AES based encryption is not recommended for encrypting images with high redundancy in their content? for example, the encryption of an image which shows a bird in the blue sky. Most of the pixels ...
1answer
217 views

### How to plot the distribution of a ciphertext?

Is there any plot or visualizing program that can plot the distribution of a plaintext and then the distribution of the ciphertext after applying a ciphering encryption algorithm? I am interested ...
1answer
175 views

### Design criteria for AES

I hope somebody can help me understand the design criterias for AES. Therefore, I would be really thankful if somebody could explain "non-linearity" in this context. A criteria for the s-box in AES ...
2answers
321 views

### Why can't Homomorphic encryption schemes support algorithms with conditions/branching?

If it isn't already apparent from the title of my question, i should make clear that I have only a very basic understanding of homomorphic encryption. I would like to know why homomorphic encryption ...
1answer
155 views

### Zero Knowledge auth schemes with weak secret

In Zero Knowledge auth schemes the public DH factor of each peer is encrypted with a potentially weak pre-shared secret and the resulting ciphertexts are exchanged over an insecure channel. Why is no ...
1answer
271 views

### Polynomial for secure communication

Can we use a polynomial $P(x)$ to securely communicate ? For example Alice & Bob agree on a degree of a polynomial. The value $x$ & the coeficients are generated from a seed using a hash ...
1answer
465 views

### SSTP MSCHAP-V2 Authentication before SSL or after SSL Session

So with the recent news that there's a lovely new tool to crack MSChapV2 packets. So the question I have is on a SSTP Connection is the MSChapv2 handshake encrypted pre SSL setup or post. Obviously ...
1answer
139 views

### Combatting traffic shape analysis with spurious packets

I was reading a question about combatting traffic analysis, and a thought occured. If I send random junk messages periodically, would that defeat traffic analysis? The messages would contain some ...
2answers
193 views

### Do these 2 KSA shortcuts weaken RC4?

Alice securely gives Bob a secret key so they can exchange 10 different messages encrypted with RC4. (Messages will include a counter for uniqueness and a MAC for authentication.) For each message ...
1answer
74 views

### How to take SHA-1 safely for my particular case?

Let me ask about my toy passwords generator program X5 which I want to improve. X5 uses a secret key and a public key to generate a password.Where any public key is supposed to be known to hackers in ...
1answer
261 views

### Can you help me understand ECC Cryptography and it's algorithm?

I want to know the basic understanding of ECC algorithm for cryptography. But I am not aware of the algorithm. Can anyone provide me with a basic explanation of the algorithm?
1answer
267 views

### How can I control the output of a hash function to output to specific data according to similarity?

I do not know if the question lies exactly in that field but I'll give it a try unless rejection. I want to study methods of applying LSH functions to feet in a specific area of digest values. ...
1answer
29 views

### Specific example of a MAC in TLS?

This seems like quite a dumb question, but I really don't know if I'm finding a answer anywhere. I understand that if i access a website that is secured with TLS, we exchange ciphersuites and so on, ...
1answer
40 views

### Explanation of the Fiat-Shamir heuristic

The Wikipedia page on the topic (http://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) is completely useless as it only explains what it is and not how it works. I looked at the original paper ...
1answer
41 views

### Is a strong block cipher usable as a strong sponge function?

From the literature, it looks like the security proofs of sponge functions depend on how well they approximate a random permutation, Since a block cipher also ideally behaves like a random permutation ...
1answer
43 views

### Is there (this) a case in which salting is dispensable?

tl;dr this is not a duplicate of "what is a salt/why use salt?" question. Instead it is specificly asking when salt may not be necessary for hashing securly? (i.e. when the data being hashed is ...
1answer
33 views

### Retrieve timestamp from TOTP value

TOTP (Time-based One-Time Password) as I understand is an algorithm that uses the current time as a variable along with a shared key to generate a secured token. Wiki page for reference: ...
1answer
50 views

### What approach is used here? [closed]

Here is an image hidding some information. I need to discover, what is the hidden text. I tried to interpret this as 27 letter alphabet(with space) in columns, tried this with Ceasar cipher. No ...
1answer
48 views

### What cipher algorithm is this routine using? [closed]

I transfered a code routine from Java to Python: ...
1answer
37 views

### Repeating something encrypted and non-encrypted?

If one wants to keep the receiver's name non encrypted, but it also appears in the encrypted message - will it leak information? (other than the receiver's name, of course.) Let's assume a "bad" case ...
1answer
94 views

### practical use of homomorphic encryption

Are RSA and Elgamal partially homomorphic techniques? which one is better if one want to use it for practical purpose? and is there some FHE technique which can be used practically?
1answer
70 views

### SHA1 - SSL/TLS Cipher Suite

SHA-1 is on the way to deprecation, in particular for digital certification (x509). But I can't find ressources about SHA-1 deprecation from SSL/TLS Cipher Suites. Is it implicit, as deprecation ...
1answer
62 views

### RSA Cryptosytsem, choosing $e$ [duplicate]

I am using the RSA crytposytem. I have $p$, $q$ and hence $n$ and $\phi$ however I don't understand how to get $e$ such that $gcd(e,\phi)=1$ Many thanks
1answer
36 views

### block cipher algorithms with variable block lengths

Rijndael supports block lengths of 128, 192 and 256. AES does not but Rijndael does. What other algorithms support variable block lengths? Or is Rijndael unique in that regard?
1answer
42 views

### Does SHA-1 hash have quasi commutative property? [closed]

Although I have tested with a program and found negative answer, I want to be sure.
1answer
56 views

### Does MD5 hash have quasi commutative property? [duplicate]

I am implementing a one-way accumulator using MD5 hash, wondering wheather it has quasi commutative property or not.
1answer
54 views

### special public keys and modulo n

I just picked up cryptography and have some questions on RSA cryptosystem: Say there are two public keys (n, e1), (n, e2), e1 is coprime to e2. They share the same n. Is it possible to find the ...
1answer
49 views

### what does rsaSha512Sign do?

I have the following function: ...
1answer
60 views

### Rabin Cryptosystem Problem (variant)

My understanding of Rabin We have p and q which are distinct primes congruent to 3 mod 4. ...
1answer
105 views

### BruteForcer XOR (bfxor.exe) to attack 64-bit keys and longer

First of all, this is not a beginner's question since I already know a good deal about encryption and brute-force attacks. This is also no question on how to code programs for brute-force attacks ...
1answer
51 views

### OpenSSL RSA same plaintext but different ciphertext

how OpenSSL RSA work ? I generate public (n,e) and private key (n,d) then I encypted a file by : ...
1answer
59 views

### Best practices (if any) to add metadata to encrypted files

I am encrypting files using AES/CBC/PKCSPadding, with 256 bits long keys. So far the first 16 bytes of each encrypted file are the IV. I would like to store some more information regarding the ...
1answer
64 views

### Fairness in cryptography

Two users A and B decided to share a file of same size and transfer data bit by bit. And at the end of exchange, A will have B's data and B will have A's data. Assuming, A starts to transfer the ...
1answer
23 views

### CSPRNG's (ELI5) What's the purpose of multiple seeds/ regenerating sources of entropy (i.e. /dev/random)?

Why is there a need to generate more than one high entropy seed? It would seem like if the original source of entropy is high quality, than some 512 bits should be more than enough to seed a CSPRNG ...
1answer
41 views

### TLS - self encrypting to avoid tls setup, secure?

I am in doubt : of course one can create a tl connection between a client and a server. But what if the client sends self encrypted with, say, blowfish, data to the server? The goal is that the ...
1answer
52 views

### Signature scheme doesnt seem to hold

I can't seem to verify this signature scheme. Taking this as an example: $p = 23$, $g = 7$, Private Key : $(12$, $20$, $3$, $18)$, $y = 16$ and $q = 2$ This will give me: $y_1 = 7$12$*16$20 \$= ...

15 30 50 per page


text:
# News for April 2020

April is now behind us, and we hope you and your families are all staying safe and healthy. We saw six seven property papers appear online last month, so at least there is some reading ahead of us! A mixture of privacy, quantum, high-dimensional distributions, and juntas (juntæ?). A lot of distribution testing, overall.

Connecting Robust Shuffle Privacy and Pan-Privacy, by Victor Balcer, Albert Cheu, Matthew Joseph, and Jieming Mao (arXiv). This paper considers a recent notion of differential privacy called shuffle privacy, where users have sensitive data, a central untrusted server wants to do something with that data (for instance, say… testing its distribution), and a trusted middle-man/entity shuffles the users’ messages u.a.r. to bring in a bit more anonymity. As it turns out, testing uniformity (or identity) of distributions in the shuffle privacy model is (i) much harder than without privacy constraints; (ii) much harder than with ‘usual’ (weaker) differential privacy (iii) much easier than with local privacy; (iv) related to the sample complexity under another privacy notion, pan-privacy. It’s a brand exciting new world out there!

(Note: for the reader interested in keeping track of identity/uniformity testing of probability distributions under various privacy models, I wrote a very short summary of the current results here.)

Entanglement is Necessary for Optimal Quantum Property Testing, by Sebastien Bubeck, Sitan Chen, and Jerry Li (arXiv). The analogue of uniformity testing, in the quantum world, is testing whether a quantum state is equal (or far from) the maximally mixed state. It’s known that this task has “quantum sample complexity” (number of measurements) $$\Theta(d/\varepsilon^2)$$ (i.e., square root dependence on the dimension of the state, $$d^2$$). But this requires entangled measurements, which may be tricky to get (or, in my case, understand): what happens if the measurements can be adaptive, but not entangled? In this work, the authors show that, under this weaker access model $$\Omega(d^{4/3}/\varepsilon^2)$$ measurements are necessary: adaptivity alone won’t cut it. It may still help though: without either entanglement nor adaptivity, the authors also show a $$\Omega(d^{3/2}/\varepsilon^2)$$ measurements lower bound.

Testing Data Binnings, by Clément Canonne and Karl Wimmer (ECCC). More identity testing! Not private and not quantum for this one, but… not quite identity testing either. To paraphrase the abstract: this paper introduces (and gives near matching bounds for) the related question of identity up to binning, where the reference distribution $$q$$ is over $$k \ll n$$ elements: the question is then whether there exists a suitable binning of the domain $$[n]$$ into $$k$$ intervals such that, once binned, $$p$$ is equal to $$q$$.”

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models, by Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda (arXiv). Back to identity testing of distributions, but for high-dimensional structured ones this one. Specifically, this paper focuses on the undirected graphical models known as restricted Boltzmann machines, and provides efficient algorithms for identity testing and conditional hardness lower bounds depending on the type of correlations allowed in the graphical models.

Robust testing of low-dimensional functions, by Anindya De, Elchanan Mossel, and Joe Neeman (arXiv). Junta testing is a classical, central problem in property testing, with motivations and applications in machine learning and complexity. The related (and equally well-motivated) question of junta testing of functions on $$\mathbb{R}^d$$ (instead of the Boolean hypercube) was recently studied by the same authors; and the related (and, again, equally well-motivated) question of tolerant junta testing on the Boolean hypercube was also recently studied (among other works) by the same authors. Well, this paper does it all, and tackles the challenging (and, for a change, equally well-motivated!) question of tolerant testing of juntas on $$\mathbb{R}^d$$.

Differentially Private Assouad, Fano, and Le Cam, by Jayadev Acharya, Ziteng Sun, and Huanyu Zhang (arXiv). Back to probability distributions and privacy. This paper provides differentially private analogues of the classical eponymous statistical inference results (Assouad’s lemma, Fano’s inequality, and Le Cam’s method). In particular, it gives ready-to-use, blackbox tools to prove testing and learning lower bounds for distributions in the differentially private setting, and shows how to use them to easily derive, and rederive, several lower bounds.

Edit: We missed one!

Learning and Testing Junta Distributions with Subcube Conditioning, by Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten (arXiv). This paper focuses on the subcube conditioning model of (high-dimensional) distribution testing, where the algorithm can fix some variables to values of its choosing and get samples conditioned on those variables. Extending and refining techniques from a previous work by a (sub+super)set of the authors, the paper shows how to optimally learn and test junta distributions in this framework—with exponential savings with respect to the usual i.i.d. sampling model.

# News for January 2020

The first month of 2020 is behind us, and it’s already looking good! Four papers last month, spanning quantum, graphs, and probability distributions.

On Efficient Distance Approximation for Graph Properties, by Nimrod Fiat and Dana Ron (arXiv). In the dense graph (i.e., adjacency-matrix) model, one is given a distance parameter $$\varepsilon$$ and granted query access to the adjacency matrix of a graph $$G$$, and seeks to determine something about the distance of $$G$$ to a prespecified property $$\mathcal{P}$$ of interest (i.e., the fraction of the matrix that needs to be changed for $$G$$ to satisfy the property). Testing requires to distinguish whether that distance is zero, or at least $$\varepsilon$$; many results over the past years have shown that many properties can be tested with a number of queries depending only on $$\varepsilon$$ (and not on $$n=|G|$$. This work focuses on the harder problem of distance estimation, or, equivalently, tolerant testing: that is, estimate this distance up to $$\pm\varepsilon$$. The authors introduce a general framework to get distance approximation algorithms from a “complicated” property by decomposing it into simpler properties and using algorithms for those. Applying this framework to a few flagship properties, they then show that $$P_3$$-freeness, induced $$P_4$$-freeness, and cordiality are properties which have efficient distance estimation algorithms (independent of $$n$$, and polynomial in $$1/\varepsilon$$).

Minimax Optimal Conditional Independence Testing, by Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman (arXiv). Given i.i.d. draws from a triple $$(X,Y,Z)$$, how hard is it to check whether $$X \perp Y \mid Z$$, that is, “$$X$$ and $$Y$$ are independent conditioned on $$Z$$ (or far from it)?” This is the problem on conditional independence testing, which was covered back in the days for the case where $$X,Y,Z$$ are discrete. Well, this new work takes the fight out of the discrete world: extending the results and techniques from the discrete case, it provides optimal bound for the continuous case: where $$Z$$ is on $$[0,1]$$, and then when all three $$X,Y, Z$$ are continuous.

How symmetric is too symmetric for large quantum speedups?, by Shalev Ben-David and Supartha Podder (arXiv); and Can graph properties have exponential quantum speedup?, by Andrew M. Childs and Daochen Wang (arXiv). Both these works independently study the relation between the (bounded-error) randomized and quantum query complexities of any graph property $$f$$, in the dense graph (adjacency-matrix) model. In particular, how much advantage do quantum algorithms provide for those?
As it turns out, not so much: for those functions, both papers show the two quantities are always polynomially related ($$R(f) \leq Q(f) \leq O(R(f)^6))$$) in the dense-graph model. As a corollary, this implies that testing any such property won’t benefit much from quantum (that is, at most polynomially)…. at least in this model. In the adjacency list model (also known as the bounded-degree graph model), the first paper conjectures that exponential query complexity improvements are possible; and the second paper provides an example, establishing it. Altogether, this fully settles an open problem of Ambainis, Childs, and Liu, and Montanaro and de Wolf.

# News for October 2019

Last month was a lean month, with only three papers: one on direct product testing, one on finding forbidden patterns in a sequence, and one (an update of a paper which we had missed in the Spring) on quantum distribution testing.

Direct sum testing – the general case, by Irit Dinur and Konstantin Golubev (ECCC). Say a function $$f\colon \prod_{i=1}^d [n_i] \to \mathbb{F}_2$$ is a direct product if it can be factored as $$f(x_1,\dots,x_d)=\sum_{i=1}^d f_i(x_i)$$, where $$f_i\colon [n_i]\to\mathbb{F}_2$$.
This paper provides a 4-query tester (i.e., a proximity oblivious tester (POT)) for the direct product property, reminiscent of (and relying on) the BLR linearity test: specifically, draw two subsets $$S,T\subseteq [d]$$ and two inputs $$x,y\in \prod_{i=1}^d [n_i]$$ u.a.r., and accept iff
$$f(x)+f(x_Sy)+f(x_Ty)+f(x_{S\Delta T}y) = 0\,.$$
The main theorem of the paper is to show that the probability that this simple test rejects is lower bounded (up to a constant factor) by the distance of $$f$$ to direct-product-ness. (The authors also provide a different POT making $$d+1$$ queries, but with a simpler analysis.)

Finding monotone patterns in sublinear time, by Omri Ben-Eliezer, Clément Canonne, Shoham Letzter, and Erik Waingarten (ECCC). Given a function $$f\colon [n]\to\mathbb{R}$$, a monotone subsequence of size $$k$$ is a $$k$$-tuple of indices $$i_1 < \dots <i_k$$ such that $$f(i_j) < f(i_{j+1})$$ for all $$j$$. This work considers (non-adaptive) one-sided testing of monotone-subsequence-freeness, or, equivalently, the task of finding such a monotone subsequence in a function promised to contain many of them. (This, in particular, generalizes the problem of one-sided monotonicity testing, which is the case $$k=2$$.) The main result is a full characterization of the query complexity of this question (for constant $$k$$): strange as the exponent may seem, $$\Theta_\varepsilon( (\log n)^{\lfloor \log_2 k\rfloor} )$$ queries are necessary and sufficient. The proof relies on a structural dichotomy result, stating that any far-from-free sequence either contains “easy to find” increasing subsequences with increasing gaps between the elements, or has a specific hierarchical structure.

Quantum Closeness Testing: A Streaming Algorithm and Applications, by Nengkun Yu (arXiv). This paper is concerned with quantum distribution testing in the local model, which only allows a very restricted (albeit, as the author argues, more natural and easier to implement) type of measurements, and is particularly well-suited to a streaming setting. The main contribution of this paper is to show a connection to classical distribution testing, allowing one to obtain quantum distribution testing upper bounds from their classical distribution testing counterparts. In more detail, the paper shows that, from local measurements to two $$d$$-dimensional quantum states $$\rho,\sigma$$, one can provide access to two classical distributions $$p,q$$ on $$\approx d^2$$ elements such that (i) $$\| p-q\|_2 \approx \|\rho-\sigma\|_2/d$$ and (ii) $$\| p\|_2,\| q\|_2 = O(1/d)$$.
Using this connection, the paper proceeds to establish a variety of upper bounds for testing several distribution properties in the local quantum model.

# Open Problems From the Workshop on Data Summarization and the Workshop on Local Algorithms

A blast from the (recent) past: the open problems from the Workshop on Data Summarization held in March 2018 in the University of Warwick have been posted online, and are available here.

Fast-forward to this summer: the recently concluded 3rd Workshop on Local Algorithms, which took place last month at ETH Zurich, featured an open problems session. The list of open problems can be found in this link, or here for a PDF version.

# News for July 2019

We saw quite an activity last month, with a total of 9 papers on property testing or related areas.

Revisiting Alphabet Reduction in Dinur’s PCP, by Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep (ECCC). As mentioned in the title, this work provides an alternate proof of one of the two parts of the Dinur’s PCP theorem proof. In that proof, the argument goes by alternating two main steps: (i) amplifying the soundness gap, at the price of increasing the alphabet size (and the instance size); (ii) reducing the alphabet size, at the price of increasing the instance size. From the observation that step (i) creates some structure in the instances that can be leveraged, the authors provide an alternative construction for (ii), leading to an arguably simpler analysis of the soundness of the underlying test. A nice throwback to some of the roots of property testing.

Then, four papers on distribution testing:
Testing Mixtures of Discrete Distributions, by Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld (arXiv). One of the most studied problems in distribution testing is identity testing (a.k.a., goodness-of-fit): given a reference distribution $$q$$ over a domain of size $$n$$ and i.i.d. samples from an unknown $$p$$, decide between $$p=q$$ and $$d_\textrm{TV}(p,q) > \varepsilon$$. While this is now well-understood and can be done with a strongly sublinear number of samples (namely, $$\sqrt{n})$$), the case of tolerant testing is much sadder: Valiant and Valiant proved that $$\Theta(n/\log n)$$ samples were required for distinguishing $$d_\textrm{TV}(p,q) < \varepsilon/2$$ from $$d_\textrm{TV}(p,q) > \varepsilon$$. So, noise-tolerance is almost as hard as it gets… except, as this works suggests and studies, if one has some guarantees on the noise! What if the noise in the completeness case was just that $$q$$ is perturbed by some (known, or available via samples as well) noise coming from a second distribution $$\eta$$? I.e., the question is now to test whether $$p$$ if of the form $$\alpha q + (1-\alpha) \eta$$ for some $$\alpha\in [0,1]$$, or if it is $$\varepsilon$$-far from all mixtures of $$q$$ and $$\eta$$. The authors have various results on this question and some extensions, but the upshot is: “with structured noise, strongly sublinear sample complexity is once again possible.”

Can Distributed Uniformity Testing Be Local?
, by Uri Meir, Dor Mintzer, and Rotem Oshman (ACM PODC Proceedings). More on identity testing, specifically uniformity testing. No noise here, but another constraint: the samples are distributed. There are $$k$$ players, each holding $$q$$ i.i.d. samples from a distribution $$p$$ over $$[n]$$; each can send $$\ell=1$$ bit to a central referee, in a non-interactive fashion. Is $$p$$ the uniform distribution, or is it $$\varepsilon$$-far from it? The authors here consider the case where $$k,n,\varepsilon$$ are fixed, and prove lower bounds on the number $$q=q(k,n,\varepsilon)$$ of samples each player must hold in order to perform this uniformity testing task. (Note: their lower bounds hold even in the public-randomness setting.) Motivated by the LOCAL model, they focus on 3 cases of interest, for which they obtain tight or near-tight bounds on $$q$$ (in view of upper bounds from previous work of a subset of the authors): (1) when the referee’s decision has to be the $$\textsf{AND}$$ of all $$n$$ bits she receives; (2) when the referee can do something more involved, and use a threshold function; and (3) when the referee can use an arbitrary function of those $$n$$ messages. Underlying those lower bounds is a neat application of Boolean Fourier analysis, recasting the analysis of the standard “Paninski” lower bound instance and the player’s decision functions as a question on Boolean functions.

Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit, by Jayadev Acharya, Clément Canonne, Yanjun Han, Ziteng Sun, and Himanshu Tyagi (arXiv,ECCC). Remember the paper just above? Now, focus on the case (3), where the referee can use any function of the message, allow each player to send $$\ell$$ bits instead of one, but give only one sample (instead of $$q$$) to each player. This becomes a setting we have talked about before on this blog (specifically, with three papers on these three months). Those three papers established the optimal number of player $$k$$, in terms of the domain size $$n$$, the distance parameter $$\varepsilon$$, and the number of bits per player $$\ell$$, in both the private-coin and public-coin settings. This new work interpolates between those two extremes, and gives the tight answer to the general question: if there are $$0\leq s \leq \log n$$ bits of public randomness available, what is the optimal number of players to perform identity testing? Behind the upper bounds is a new notion of (randomness-efficient) domain compression they introduce: how to reduce the domain size of the probability distributions while preserving the $$\ell_1$$ distances between them as much as possible?

Towards Testing Monotonicity of Distributions Over General Posets, by Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee (arXiv). Away from identity testing, let’s now consider another central question, testing monotonicity of distributions. Specifically, a distribution $$p$$ over a given poset $$(\mathcal{X}, \prec)$$ is said to be monotone if $$p(x) \leq p(y)$$ whenever $$x\prec y$$. While the question is fully understood for the familiar case of the line $$\mathcal{X} = \{1,2,\dots,n\}$$, the case of general posets is much murkier, and more or less uncharted. This paper initiates a general study of the question, improving on previously known bounds for the matching poset and Boolean hypercube, and providing several new results and techniques for the general case, to establish both upper and lower bounds on the sample complexity.

And now… graphs!
Expansion Testing using Quantum Fast-Forwarding and Seed Sets, by Simon Apers (arXiv). This paper is concerned with (bicriteria) testing of vertex expansion of a given graph $$G=(V,E)$$ in the bounded-degree graph model. Loosely speaking, given a value $$\Phi$$ and query access (i.e., sampling a node u.a.r., querying the degree of a node, and querying the $$i$$-th neighbor of a node) to a graph $$G$$ with maximum degree $$d=\Theta(1)$$, the goal is to distinguish between (i) $$G$$ has vertex expansion at most $$\Phi$$ and (ii) $$G$$ is $$\varepsilon$$-far from any $$G’$$ with vertex expansion at most $$\Phi^2$$ (simplifying and dropping some technicalities). The previous state-of-the-art was a $$\tilde{O}_{\varepsilon}(n^{1/2}/\Phi^2)$$ query complexity for classical algorithms, and a $$\tilde{O}_{\varepsilon}(\min(n^{1/3}/\Phi^2),n^{1/2}/\Phi^2))$$ query complexity upper bound for quantum testers. The current work improves on this by providing a $$\tilde{O}_{\varepsilon}(n^{1/3}/\Phi)$$ quantum tester. Graphs expand—and so does the gap between classical and quantum testing.

Walking Randomly, Massively, and Efficiently, by Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski (arXiv). One very useful primitive, in many graph property testing results and of course well beyond property testing, is the ability to perform random walks on graphs. In the case of large, distributed (or merely impractically massive) graphs, however, it is not clear how to implement this primitive efficiently. This work addresses this question in the MPC (Massive Parallel Computation) model, and shows how to perform independently, from all of the $$n$$ nodes of a graph (i.e., machine), an $$\ell$$-length random walk with only $$O(\log \ell)$$ rounds of communication and $$O(n^\alpha)$$ space per machine, for any constant $$\alpha \in(0,1)$$. This round complexity matches a known (conditional) lower bound, and thus the result is as good as it gets — further, the authors obtain such MPC algorithms for both undirected and directed graph, somehow leveraging the latter case to handle the (significantly more complicated) directed case. As an application of this efficient random walk primitive, they provide MPC property testing algorithms for both bipartiteness and vertex expansion (same definition as in the paper above: vertex expansion $$\Phi$$ vs. $$\varepsilon$$-far from any $$G’$$ with vertex expansion $$\Phi^2$$) in the general graph model. (Beyond property testing, another application—the main one in the paper— is computing PageRank in both graphs and directed graphs.)

A Lower Bound on Cycle-Finding in Sparse Digraphs
, by Xi Chen, Tim Randolph, Rocco Servedio, and Timothy Sun (arXiv). In this paper, the authors tackle the problem of one-sided testing of acyclicity of directed graphs, in the bounded-degree graph model (equivalently, on the task of finding a cycle in a digraph promised to be far from acyclic). Previously, an $$\Omega(\sqrt{n})$$ lower bound for this task had been shown by Bender and Ron, based on a birthday-paradox-type argument; this work improves on this hardness result, showing that $$\tilde{\Omega}(n^{5/9})$$ queries are necessary. Interestingly, whether achieving any $$o(n)$$ query complexity is possible remains open.

Constant-Time Dynamic $$(\Delta+1)$$-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing, by Monika Henzinger and Pan Peng (arXiv). Finally, the last paper covered this month is concerned with dynamic graph algorithms: where updates to a graph (which can be both edge additions and deletions) come sequentially, and the objective is to maintain, e.g., a coloring, or an approximation of some function of the graph, at any time using as little time per update. This paper advocates the use of techniques from property testing (loosely speaking, as their locality and query-efficiency translates to fast update times) to design better dynamic graph algorithms. It illustrates this idea by obtaining several new results, in particular an (amortized) $$O(1)$$-update-time randomized algorithm to maintain a $$(\Delta+1)$$-coloring in a graph with degree bound $$\Delta$$. The algorithm relies on a random ranking of the nodes which, combined with a suitable randomized update rule for recoloring a vertex when needed, ensure that the recolorings will not (with high probability) “propagate” to much. This is the first time that this idea, previously used in several testing and sublinear-time papers, is used in the context of dynamic graph algorithms—adding an edge between the two areas, hopefully only the first of many.

Update: we did miss a paper! Make it ten in July…
Nearly optimal edge estimation with independent set queries, by Xi Chen, Amit Levi, Erik Waingarten (arXiv). Consider the following type of access to an unknown graph $$G=(V,E)$$ on $$n=|V|$$ nodes: on query $$S\subseteq V$$, the oracle returns 1 if $$S$$ is is an independent set, and 0 otherwise. (This sounds quite a bit like what is allowed in the group testing literature.) How many such queries are necessary to get a multiplicative estimate of the number of edges, $$m=|E|$$? In this paper, the authors improve on the previous bound of $$\min(\sqrt{m}, n^2/m)$$ (ignoring logarithmic factors), obtaining an $$\min(\sqrt{m}, n/m)$$ upper bound — complemented by a (nearly, up to those pesky log factors) matching lower bound.

If we missed a paper this month, or represented some result above, please mention it in the comments.

# News for April 2019

After a quite slow month of March, things sped up quite significantly in April: six different papers, ranging from graph testing to function testing to quantum distribution testing!

Update (05/04): We missed one. Seven!

Junta correlation is testable, by Anindya De, Elchanan Mossel, and Joe Neeman (arXiv). Junta testing really has seen a lot of attention and progress over the pass couple years! In this new work, the focus is on the tolerant version of (Boolean) junta testing, where the goal is to decide whether a given function $$f\colon \{-1,1\}^n\to \{-1,1\}$$ is close to some $$k$$-junta, or far from any such simple function. The current paper improves on previous work of Blais, Canonne, Eden, Levi, and Ron, which showed how to distinguish between $$\varepsilon$$-close to $$k$$-junta and $$16\varepsilon$$-far from $$k$$-junta in $$O_{k,\varepsilon}(1)$$ queries, in two ways: (i) the gap-factor of 16 can now be made arbitrarily small, yielding the first fully tolerant non-trivial junta tester; and (ii) the new algorithm also identifies the underlying “core junta” (up to permutation of the coordinates). Besides the other results contained in the paper (such as results for a relaxation of the tolerant question akin to that of Blais et al.), a key aspect of this paper is to go beyond the use of (set) influence as a proxy for distance to junta-ness which underlied all previous work, thus potentially opening a new avenue towards get fully tolerant, $$\mathrm{poly}(k,1/\varepsilon)$$-query junta testing algorithms.

Testing Tensor Products, by Irit Dinur and Konstantin Golubev (arXiv). In this paper, the authors consider the following testing question: given query access to a Boolean function $$f\colon [n]^d \to \mathbb{F}_2$$, test whether $$f$$ is of the form $$f(x) = f_1(x_1)+\dots f_d(x_d)$$ (equivalently, this is the task of testing whether a $$d$$-dimensional tensor with $$\pm 1$$ is of rank $$1$$). They provide two different proximity-oblivious testers (POT) for this task: a $$4$$-query one, reminiscent and building upon the BLR linearity test; as well as a $$(d+1)$$-query POT (which they dub “Shapka Test,” one can assume for their love of warm and comfortable hats), whose analysis is significantly simpler.

Changing direction, the next paper we saw is concerned with quantum testing of (regular, good ol’ classical) probability distributions:

Quantum Algorithms for Classical Probability Distributions, by Aleksandrs Belovs (arXiv). This work on quantum distribution testing considers 4 of the existing models of access to samples from an unknown probability distribution, analyzes their relationship, and argues their merits. Further, the autho establishes that for the simple hypothesis testing question of distinguishing between two (known, fixed) probability distributions $$p,q$$, in all four models the optimal sample complexity is proportional to the inverse of the Hellinger distance between $$p$$ and $$q$$—in contrast to the classical setting, where it is known to be proportional to the squared inverse of this distance.

Turning to graphs, the next work considers clustering of bounded-degree graphs, a topic we recently discussed as well:

Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs, by Pan Peng (arXiv). Consider the following noisy model: an unknown bounded-degree graph (of maximum degree $$d$$) $$G$$ which is $$(k, \phi_{\rm in},\phi_{\rm out})$$-clusterable (i.e., clusterable in at most $$k$$ clusters of inner and outer conductances bounded by $$\phi_{\rm in},\phi_{\rm out}$$) is adversarially modified in at most $$\varepsilon d n$$ edges between clusters. This noise model, introduced in this work, leads to the natural questions of “recovering the underlying graph $$G$$”: this is what the author tackles, by designing sublinear-time local clustering oracles and local reconstruction algorithms (local filters) in this setting. Further, in view of the noise model reminiscent of property testing in the bounded-degree graph setting, connections to testing clusterability are discussed; the implications of the results for testing clusterability are discussed in Section 1.4.

A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems, by Sebastian Forster and Liu Yang (arXiv). The authors focus on the problem of finding an edge (or vertex) cut in a given graph from a local viewpoint, i.e., in the setting of local computation algorithms, and provide a slew of results in detecting bounded-size cuts. This in turn has direct implications for testing $$k$$-edge and $$k$$-vertex connectivity, directed and undirected, in both the bounded-degree and general (unbounded degree) models, improving on or subsuming the current state-of-the-art across the board (see Section 1.2.4 of the paper, and the very helpful Tables 3 and 4, for a summary of the improvements).

Random walks and forbidden minors II: A $$\mathrm{poly}(d\varepsilon^−1)$$-query tester for minor-closed properties of bounded degree graphs, by Akash Kumar, C. Seshadhri, and Andrew Stolman (ECCC). Following their breakthrough from last May, the authors are at it again! Leveraging a random-walk approach, they resolve the following open question in testing bounded-degree graph: is there a $$\mathrm{poly}(1/\varepsilon)$$-query tester for planarity (and, more generality, for minor-closed graph properties)? The previous state-of-the-art, due to Levi and Ron, had a quasipolynomial dependence on $$1/\varepsilon$$.
Without spoiling too much: the answer to the open question is yes— and further the authors settle it by showing an even more general result on testing $$H$$-freeness (for any constant-size graph $$H$$).

Update (05/04):

Testing Unateness Nearly Optimally, by Xi Chen and Erik Waingarten (arXiv). Recall that a function $$f\colon \{0,1\}^n\to \{0,1\}$$ is said to be unate if there exists some $$s\in\{0,1\}^n$$ such that $$f(\cdot \oplus s)$$ is monotone; i.e., if $$f$$ is either non-increasing or non-decreasing in each coordinate. Testing unateness has seen a surge of interest over the past year or so; this work essentially settles the question, up to polylogarithmic factors in $$n$$ (and the exact dependence on $$\varepsilon$$). Namely, the authors present and analyze an $$\tilde{O}(n^{2/3}/\varepsilon^2)$$-query adaptive tester for unateness, which nearly matches the $$\tilde{\Omega}(n^{2/3})$$-query lower bound for adaptive testers previously established by Chen, Waingarten, and Xie.

# News for March 2019

Last month was very calm. Eerily calm in fact: no property testing or related sublinear-time algorithm in view!* Gird your loins for the April batch, I reckon?

$${}^\ast$$ That we saw, at least. if we missed some, please mention it in the comments below!)

Update: As mentioned in the comments, we did indeed missed two (related) works on distribution estimation from a competitive viewpoint. Namely, for a large class of properties (entropy, distance to uniformity, support size…), Hao, Orlitsky, Suresh, and Wu provide in the first paper (arXiv 1904.00070) an “instance-optimal(ish)” estimator which does “as well” with $$m/\sqrt{\log m}$$ samples than the natural and naive empirical estimator would do with $$m$$ (thus, in some sense, amplifying the data size). In the following paper (arXiv 1903.01432), Hao and Orlitsky improve this and remove the “ish” to get the optimal amplification $$m/\log m$$.

# News for December 2018

Happy near year, and best wishes to those close and $$\varepsilon$$-far! December concluded the year with 4 new preprints, spanning quite a lot of the property testing landscape:

Testing Stability Properties in Graphical Hedonic Games, by Hendrik Fichtenberger and Anja Rey (arXiv). The authors of this paper consider the problem of deciding whether a given hedonic game possesses some “coalition stability” in a property testing framework. Namely, recall that a hedonic game is a game where players (nodes) form coalitions (subsets of nodes) based on their individual preferences and local information about the considered coalition, thus resulting in a partition of the original graph.
Several notions exist to evaluate how good such a partition is, based on how “stable” the given coalitions are. This work focuses on hedonic games corresponding to bounded-degree graphs, introducing and studying the property testing question of deciding (for several such notions of stability) whether a given game admits a stable coalition structure, or is far from admitting such a partition.

Spectral methods for testing cluster structure of graphs, by Sandeep Silwal and Jonathan Tidor (arXiv). Staying among bounded-degree graphs, we turn to testing clusterability of graphs, the focus of this paper. Given an $$n$$-node graph $$G$$ of degree at most $$d$$ and parameters $$k, \phi$$, say that $$G$$ is $$(k, \phi)$$-clusterable if it can be partitioned in $$k$$ parts of inner conductance at least $$\phi$$.
Analyzing properties of a random walk on $$G$$, this work gives a bicriterion guarantee ($$(k, \phi)$$-clusterable vs. $$\varepsilon$$-far from $$(k, \phi^\ast)$$-clusterable, where $$\phi^\ast \approx \varepsilon^2\phi^2$$) for the case $$k=2$$, improving on previous work by Czumaj, Peng, and Sohler’15.

We then switch from graphs to probability distributions with our third paper:

Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction, by Jayadev Acharya, Clément Canonne, and Himanshu Tyagi (arXiv). (Disclaimer: I’m one of the authors.) In this paper, the first of an announced series of three, the authors generalize the settings of two previous works we covered here and there to consider the general question of distribution testing and learning when the $$n$$ i.i.d. samples are distributed among $$n$$ players, which each can only communicate their sample to the central algorithm by respecting some pre-specified local information constraint (e.g., privacy, or noise, or communication budget). This paper develops a general lower bound framework to study such questions, with a systematic focus on the power of public vs. private randomness between the $$n$$ parties, and instantiate it to obtain tight bounds in the aforementioned locally private and communication-limited settings. (Spoiler: public randomness strictly helps, but not always.)

Finally, after games, graphs, and distributions, our fourth paper of the month concerns testing of functions:

Partial Function Extension with Applications to Learning and Property Testing, by Umang Bhaskar and Gunjan Kumar (arXiv). This work focuses on a problem quite related to property testing, that of partial function extension: given as input $$n$$ pairs point/value from a purported function on a domain $$X$$ of size $$|X| > n$$, one is tasked with deciding whether there does exist (resp., with finding) a function $$f$$ on $$X$$ consistent with these $$n$$ values which further satisfies a specific property, such as linearity or convexity. This is indeed very reminiscent of property testing, where one gets to query these $$n$$ points and must decide (approximate) consistency with such a well-behaved function. Here, the authors study the computational hardness of this partial function extension problem, specifically for properties such as subadditivity and XOS (a sub-property of subadditivity); and as corollaries obtain new property testers for the classes of subadditive and XOS functions.

As usual, if you know of some work we missed from last December, let us know in the comments!

# News for September 2018

Last month was slower than usual, with only one property testing paper. We did miss a few papers, so hopefully this list is now up to date.

Property testing and expansion in cubical complexes, by David Garber, Uzi Vishne (arXiv). Consider the question of testing if an arbitrary function $$f\colon V\times V \to\{-1,1\}$$ is of the form $$f(x,y) = h(x)h(y)$$ for some $$h\colon V\to\{-1,1\}$$. An intuitive one-sided test, shown to work by Lubotzky and Kaufman (2014), is to pick uniformly random $$x,y,z\in V$$ and check that $$f(x,y)f(y,z)f(z,x)=1$$. This paper considers the high-dimensional generalization of testing the property that a function$$f\colon V\times V \times V\times V \to\{-1,1\}$$ is of the form $$f(w,x,y,z) = \alpha\cdot h(w,x)h(y,x)h(y,z) h(w,z)$$, for some $$h\colon V\times V\to\{-1,1\}$$ and sign $$\alpha\in\{-1,1\}$$. The authors derive necessary and sufficient conditions for testability of this property, by formulating it in the language of incidence geometry and exploiting this connection.

Local Computation Algorithms for the Lovász Local Lemma, by Dimitris Achlioptas, Themis Gouleakis and Fotis Iliopoulos (arXiv). There has been significant work in the past decade on constructive versions of the Lovász Local Lemma (LLL), since the seminal work of Moser-Tardos. This paper designs news Local Computation Algorithms (LCAs) for the LLL. It’s best to consider the problem of $$k$$-SAT. Consider a $$k$$-CNF $$\phi$$ with $$n$$ variables, $$m$$ clauses, where every variable is in at most $$d$$ clauses. By the LLL, if $$d \leq 2^k/ke$$, then $$\phi$$ is satisfiable. An LCA would compute any bit of a satisfying assignment, by making sublinear queries into $$\phi$$. This was first studied by Rubinfeld-Tamir-Vardi-Xie. Their LCA would make polylogarithmically many queries, but requires a stronger condition that what LLL achieves. This paper gives the first sublinear LCA with precisely the LLL conditions, though the number of queries is $$n^\beta$$ (for $$\beta \lt 1$$). The main result is an LCA for an abstract LLL formulation, that also leads to LCAs for graph coloring. Roughly speaking, for a graph with maximum degree $$\Delta$$ where all neighborhoods are sufficiently far from cliques, the LLL shows that the chromatic number bound of $$\Delta + 1$$ can be beaten. This result gives an LCA for graph coloring under these LLL conditions.

Sublinear Time Low-Rank Approximation of Distance Matrices, by Ainesh Bakshi and David P. Woodruff (arXiv). Consider two sets of points $$P$$ and $$Q$$ in a metric space, with $$m$$ and $$n$$ points respectively. The $$m \times n$$ distance matrix $$A$$ contains all pairwise distances between them. This paper studies approximating $$A$$ using a low rank representation, without reading all the entries in $$A$$. The main result is as follows. For rank parameter $$k$$, let $$A_k$$ be the closest (by Frobenius norm) rank-$$k$$-approximation to $$A$$. There is a $$O(m^{1+\gamma} + n^{1+\gamma}poly(k\epsilon^{-1}))$$ (for arbitrary $$\gamma > 0$$) algorithm that outputs a rank $$k$$-matrix $$B$$ with the following property: $$\|A-B\|^2_F \leq \|A-A_k\|^2_F + \epsilon \|A\|^2_F$$. Interestingly, there is a lower bound showing that a $$o(mn)$$ algorithm cannot get a multiplicative approximation. One technical ingredient is a method to sample column norms of $$A$$, under an approximate triangle inequality constraint. This allows one to compute smaller matrices that approximate $$A$$, on which one can directly compute an approximate rank-$$k$$ decomposition.

On Solving Linear Systems in Sublinear Time, by Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow (arXiv). Solving Laplacian linear systems is an immensely deep area, with lots of exciting recent work. This paper studies sublinear algorithms for such problems. Consider a Laplacian matrix $$L$$ (think of $$I – A/d$$, for adjacency matrix $$A$$ of a $$d$$-regular graph). The aim is to solve $$Lx = b$$, for $$x, b \in {\mathbb R}^n$$. Let the solution be $$x^*$$. The main result shows that one can approximate any entry in sublinear time. Specifically, for any coordinate $$i$$, one can output an approximate $$\hat{x_i}$$ such that $$|\hat{x_i} – x^*_i| \leq \|x^*\|_\infty$$. The running time is essentially $$d\epsilon^{-2}\kappa^3$$, where $$\kappa$$ is a bound on the condition number of $$L$$. There are generalizations for Symmetrically Diagonally Dominant (SDD) matrices, a generalization of Laplacians. There is an $$\Omega(n^{1/d^2})$$ lower bound for solving general PSD systems, and a lower bound showing that $$\Omega(\kappa^2)$$ queries into $$b$$ are necessary.

# News for June 2018

The summer gets off to a flying start, with three property testing papers, spanning differential privacy, distribution testing, and juntas in Gaussian space!

On closeness to $$k$$-wise uniformity, by Ryan O’Donnell and Yu Zhao (arXiv)
In this paper, the authors consider the following structural question about probability distributions over the Boolean hypercube $$\{-1,1\}^n$$: ” what is the relation between total variation distance $$\delta$$ to $$k$$-wise independence, and bound $$\varepsilon$$ on the Fourier coefficients of the distribution on degrees up to $$k$$?”

While this question might seem a bit esoteric at first glance, it has direct and natural applications to derandomization, and of course to distribution testing (namely, to test $$k$$-wise independence and its generalization, $$(\varepsilon, k)$$-wise independence of distributions over the hypercube).

The main contribution here is to improve (by a $$(\log n)^{O(k)}$$ factor) the bounds on $$\delta (n,k,\varepsilon)$$ over the previous work by Alon et al. [AAK+07], making them either tight (for $$k$$ even) or near-tight. To do so, the authors introduce a new hammer to the game, using linear programming duality in the proof of both their upper and lower bounds.

Property Testing for Differential Privacy, by Anna Gilbert and Audra McMillan (arXiv)
Differential privacy, as introduced by Dwork et al., needs no introduction. Property testing, especially on this website, needs even less. What about a combination of the two? Namely, given black-box access to an algorithm claiming to perform a differentially private computation, how to test whether this is indeed the case?

Introducing and considering this quite natural question for the first time [01/31/2019: see erratum below], this work shows, roughly speaking, that testing differential privacy is hard. Specifically, they show that for many notions of differential privacy (pure, approximate, and their distributional counterparts), testing is either impossible or possible but not with a sublinear number of queries (even when the tester is provided with side information about the black-box). In other terms, as the authors put it: trusting the privacy of an algorithm “requires compromise by either the verifier or algorithm owner” (and, in the latter case, even then it’s not a simple matter).

Is your data low-dimensional?, by Anindya De, Elchanan Mossel, and Joe Neeman (arXiv)
(Well, is it?) To state it upfront, I am biased here, as it is a problem I was very eager to see investigated to begin with. To recap, the question is as follows: “given query access to some unknown Boolean-valued function $$f\colon \mathbb{R}^n \to \{-1,1\}$$ over the high-dimensional space $$\mathbb{R}^n$$ endowed with the Gaussian measure, how can one check whether $$f$$ only depends on “few” (i.e., $$k \ll n$$) variables?”

This is the continuous, Gaussian version of the (quite famous) junta testing problem, which has gathered significant attention over the past years (the Gaussian version has, to the best of my knowledge, never been investigated). Now, the above formulation has a major flaw: specifically, it is uninteresting. In Gaussian space*, who cares about the particular basis I expressed my input vector in? So a more relevant question, and that that the authors tackle, is the more robust and natural one: “given query access to some unknown Boolean-valued function $$f\colon \mathbb{R}^n \to \{-1,1\}$$ over the high-dimensional space $$\mathbb{R}^n$$ endowed with the Gaussian measure, how can one check whether $$f$$ only depends on a low-dimensional linear combination of the variables?” Or, put differently, does all the relevant information for $$f$$ live in a low-dimensional subspace?

De, Mossel, and Neeman show how can do this, non-adaptively, with a query complexity independent of the dimension $$n$$ (hurray!), but instead polynomial in $$k$$, the distance parameter $$\varepsilon$$, and the surface area $$s$$ of $$f$$. And since this last parameter may seem quite arbitrary, they also proceed to show that a polynomial dependence in this $$s$$ is indeed required.

*”In Gaussian space, no one can hear you change basis?”

Erratum (01/31/2019): It was brought to our attention that our overview of “Property Testing for Differential Privacy” was overlooking a key part of the literature; specifically, a work of Dixit et al. (TCC 2013)  which introduces this very question. From the abstract:

How does one ensure that [those third-parties] have implemented their algorithms in a way which meet the specifications of the privacy requirements? […] In this work, we propose a new approach to the above problem which we call privacy testing. We do this by formulating the above problem in the well-studied framework of property testing.


text:
# Manipulating definitions while reading them with Get

In order to read in a definition with certain parameters replaced by appropriate values I can use for example

Block[{a=1.1,b=2.2}, Get["file"]]

where "file" is a file containing the definitions (which contain a and b on the RHS). This works well and is fast. Now is there a way to do something similar if I want to replace a string. So basically, Block[{"string"="bla"},Get["file"]] (but then in a way that actually works of course).

Try this:

Get @ StringToStream @ StringReplace["\"string\"" -> "\"bla\""] @ Import["file", "Text"]

Alternatively you can read a package step by step like in a/124670 but instead of:

Sow[ Interpretation @@ {withContext[expr], expr} ];
ReleaseHold[expr];

do

ReleaseHold[expr /. "string" -> "bla"]