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 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 = ( N B ) / 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 ( N B ) / 3 , contradicting the fact that there are at least M marks. ◼
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.
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 ρ , 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 ∈ { 0 , 1 } m such that Pr x [ C ( x , y 0 ) = f ( x ) ] ≥ ρ .
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 ] ≥ ρ then Pr [ Z ≥ ρ ] > 0 (this holds since E [ Z ] is the weighted average of Z and clearly if the average of some values is at least ρ then one of the values must be at least ρ ).
This argument has wide use in complexity theory (e.g. proving B P P ⊊ P / p o l y ) and cryptography (e.g. proving that indistinguishable encryption results in semantic security). A plethora of such applications can be found in Goldreich's books.
