en>AnomieBOT: Dating maintenance tags: {{Rewrite}}

2013-11-02T13:41:18Z

Dating maintenance tags: {{Rewrite}}

New page

In [[computational complexity theory]] and [[cryptography]], '''averaging argument''' is a standard argument for proving theorems. It usually allows us to convert [[Randomized algorithm|probabilistic]] [[polynomial-time]] algorithms into [[Circuit complexity|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 <math>N</math> people and B books. Each person likes at least <math>B/3</math> of the books. Let people leave a mark on the book they like. Then, there will be at least <math>M=(NB)/3</math> marks. The averaging argument claims that there exists a book with at least <math>N/3</math> marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than <math>N/3</math> marks. However, since there are <math>B</math> books, the total number of marks will be fewer than <math>(NB)/3</math>, contradicting the fact that there are at least <math>M</math> marks. <math>\scriptstyle\blacksquare</math>

== Formalized definition of averaging argument ==

<div style="border: 1.5px dotted #008000">
Consider two sets: X and Y, a proposition <math>p \colon X\times Y \to \text{TRUE/FALSE}</math>, and a fraction <math>f</math> (where <math>0\le f\le 1</math> ).

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

Another formal (and more complicated) definition is due to Barak:<ref>[[Boaz Barak]], [http://www.cs.princeton.edu/courses/archive/spr06/cos522/averaging.pdf "Note on the averaging and hybrid arguments and prediction vs. distinguishing."], COS522, Princeton University, March 2006.</ref>

<div style="border: 1.5px dotted #008000">
Let <math>f</math> be some function. The averaging argument is the following claim: if we have a circuit <math>C</math> such that <math>C(x, y) = f(x)</math> with probability at least <math>\rho</math>, where <math>x</math> is chosen at random and <math>y</math> is chosen independently from some [[Probability distribution|distribution]] <math>Y</math> over <math>\{0, 1\}^m</math> (which might not even be [[efficiently sampleable]]) then there exists a '''single''' string <math>y_0 \in \{0, 1\}^m</math> such that <math>\Pr_x[C(x, y_0) = f(x)] \ge \rho</math>.

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

: <math> \Pr_{x,y}[C(x, y) = f(x)] = E_y[p_y] \, </math>

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

== Application ==
This argument has wide use in [[Computational complexity theory|complexity theory]] (e.g. proving <math>\mathcal{BPP}\subsetneq\mathcal{P}/\text{poly}</math>) and [[cryptography]] (e.g. proving that [[Ciphertext indistinguishability|indistinguishable encryption]] results in [[semantic security]]). A plethora of such applications can be found in [[Oded Goldreich|Goldreich]]'s books.<ref name="goldreichbook1">[[Oded Goldreich]], ''Foundations of Cryptography, Volume 1: Basic Tools'', Cambridge University Press, 2001, ISBN 0-521-79172-3</ref><ref name="goldreichbook2">[[Oded Goldreich]], ''Foundations of Cryptography, Volume 2: Basic Applications'', Cambridge University Press, 2004, ISBN 0-521-83084-2</ref><ref name="goldreichbook3">[[Oded Goldreich]], ''Computational Complexity: A Conceptual Perspective'', Cambridge University Press, 2008, ISBN 0-521-88473-X</ref>

== References ==
{{reflist}}

{{Cryptography navbox}}

{{DEFAULTSORT:Averaging Argument}}
[[Category:Computational complexity theory]]
[[Category:Circuit complexity]]
[[Category:Probabilistic complexity theory]]
[[Category:Theory of cryptography]]

Financial independence - Revision history

en>AnomieBOT: Dating maintenance tags: {{Rewrite}}