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.
