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.
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 they 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 fewer than marks. However, since there are books, the total number of marks will be fewer than , contradicting the fact that there are at least marks.
Formalized definition of averaging argument
Another formal (and more complicated) definition is due to Barak:
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.
- Boaz Barak, "Note on the averaging and hybrid arguments and prediction vs. distinguishing.", COS522, Princeton University, March 2006.
- 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