Financial independence

In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits.

Example

To simplify, let's first consider an example.

Example: If every person likes at least 1/3 of the books in a library, then, there exists a book, which at least 1/3 of people liked it.

Proof: Suppose there are $N$ people and B books. Each person likes at least $B/3$ of the books. Let people leave a mark on the book they like. Then, there will be at least $M=(NB)/3$ marks. The averaging argument claims that there exists a book with at least $N/3$ marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than $N/3$ marks. However, since there are $B$ books, the total number of marks will be fewer than $(NB)/3$, contradicting the fact that there are at least $M$ marks. $◼$

Formalized definition of averaging argument

Consider two sets: X and Y, a proposition $p:X\times Y\to \text{TRUE/FALSE}$, and a fraction $f$ (where $0\le f\le 1$ ).

If for all $x\in X$ and at least a fraction $f$ of $y\in Y$, the proposition $p(x,y)$ holds, then there exists a $y\in Y$, for which there exists a fraction $f$ of $x\in X$ that the proposition $p(x,y)$ holds.

Another formal (and more complicated) definition is due to Barak:

Let $f$ be some function. The averaging argument is the following claim: if we have a circuit $C$ such that $C(x,y)=f(x)$ with probability at least $\rho$, where $x$ is chosen at random and $y$ is chosen independently from some distribution $Y$ over $\{0,1{\}}^m$ (which might not even be efficiently sampleable) then there exists a single string $y_0\in \{0,1{\}}^m$ such that ${\mathrm{Pr}}_x[C(x,y_0)=f(x)]\ge \rho$.

Indeed, for every $y$ define $p_y$ to be ${\mathrm{Pr}}_x[C(x,y)=f(x)]$ then

${\mathrm{Pr}}_{x,y}[C(x,y)=f(x)]=E_y[p_y]$

and then this reduces to the claim that for every random variable $Z$, if $E[Z]\ge \rho$ then $\mathrm{Pr}[Z\ge \rho ]>0$ (this holds since $E[Z]$ is the weighted average of $Z$ and clearly if the average of some values is at least $\rho$ then one of the values must be at least $\rho$).

Application

This argument has wide use in complexity theory (e.g. proving $\mathcal{ℬ}\mathcal{𝒫}\mathcal{𝒫}⊊\mathcal{𝒫}/\text{poly}$) and cryptography (e.g. proving that indistinguishable encryption results in semantic security). A plethora of such applications can be found in Goldreich's books.

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.