# 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. $\blacksquare$ ## Formalized definition of averaging argument

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

## 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.