Averaging argument

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

Let X and Y be sets, let p be a predicate on X × Y and let f be a real number in the interval [0, 1]. If for each x in X and at least f |Y| of the elements y in Y satisfy p(x, y), then there exists a y in Y such that there exist at least f |X| elements x in X that satisfy p(x, y).

There is another definition, defined using the terminology of probability theory.^[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)]\geq \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]\geq \rho$ then $\Pr[Z\geq \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 ${\mathsf {BPP}}\subsetneq {\mathsf {P/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

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

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Category Portal WikiProject

This article is issued from Wikipedia - version of the 10/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.