# Averaging argument

Jump to: navigation, search

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. $\scriptstyle\blacksquare$

## Formalized definition of averaging argument

Consider two sets: X and Y, a proposition $p \colon 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:[1]

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 $\Pr_x[C(x, y_0) = f(x)] \ge \rho$.

Indeed, for every $y$ define $p_y$ to be $\Pr_x[C(x, y) = f(x)]$ then

$\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 $\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{BPP}\subsetneq\mathcal{P}/\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.[2][3][4]

## References

1. ^ Boaz Barak, "Note on the averaging and hybrid arguments and prediction vs. distinguishing.", COS522, Princeton University, March 2006.
2. ^ Oded Goldreich, Foundations of Cryptography, Volume 1: Basic Tools, Cambridge University Press, 2001, ISBN 0-521-79172-3
3. ^ Oded Goldreich, Foundations of Cryptography, Volume 2: Basic Applications, Cambridge University Press, 2004, ISBN 0-521-83084-2
4. ^ Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X