User:Sadeq/Averaging lemma

The averaging argument is a standard argument which helps in proving theorems in complexity theory and cryptography. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits.

Example

edit

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   people and B books. Each person likes at least   of the books. Let people leave a mark on the book the like. Then, there will be at least   marks. The averaging argument claims that there exists a book with at least   marks on it. Assume, to the contradiction, that no such book exists. Then, every book has less than   marks. But, since there are   books, the total number of marks will be less than  , contradicting the fact that there is at least   marks.  

Formalized Definition of Averaging Argument

edit

Consider two sets: X and Y, a proposition   , and a fraction   (where   ).

If for all   and at least a fraction   of   , the proposition   holds, then there exists a   , for which there exists a fraction   of   that the proposition   holds.

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

Let   be some function. The averaging argument is the following claim: if we have a circuit   such that   with probability at least  , where   is chosen at random and   is chosen independently from some distribution   over   (which might not even be efficiently sampleable) then there exists a single string   such that  .

Indeed, for every   define   to be   then

 

and then this reduces to the claim that for every random variable  , if   then   (this holds since   is the weighted average of   and clearly if the average of some values is at least   then one of the values must be at least  ).

Application

edit

This argument has wide use in complexity theory (e.g. proving  ) 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

edit
  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

[[Category:Computational complexity theory]] [[Category:Circuit complexity| ]] [[Category:Probabilistic complexity theory| ]] [[Category:Cryptography]] [[Category:Theory of cryptography]]