(This is the sixth in a series of posts on online optimization techniques and their “applications” to complexity theory, combinatorics and pseudorandomness. The plan for this series of posts is to alternate one post explaining a result from the theory of online convex optimization and one post explaining an “application.” The first two posts were about the technique of multiplicative weight updates and its application to “derandomizing” probabilistic arguments based on combining a Chernoff bound and a union bound. The third and fourth post were about the Follow-the-Regularized-Leader framework, and how it unifies multiplicative weights and gradient descent, and a “gradient descent view” of the Frieze-Kannan Weak Regularity Lemma. The fifth post was about the constrained version of the Follow-the-Regularized-Leader framework, and today we shall see how to apply that to a proof of the Impagliazzo Hard-Core Lemma.)
1. The Impagliazzo Hard-Core Lemma
The Impagliazzo Hard-Core Lemma is a striking result in the theory of average-case complexity. Roughly speaking, it says that if is a function that is “weakly” hard on average for a class
of “efficiently computable” functions
, that is, if, for some
, we have that
then there is a subset of cardinality
such that
is “strongly” hard-on-average on
, meaning that
for a small . Thus, the reason why functions from
make a mistake in predicting
at least a
fraction of the times is that there is a “hard-core” set
of inputs such that every function from
makes a mistake about 1/2 of the times for the
fraction of inputs coming from
.
The result is actually not literally true as stated above, and it is useful to understand a counterexample, in order to motivate the correct statement. Suppose that contains just
functions, and that each function
differs from
in exactly a
fraction of inputs from
, and that the set of mistakes are disjoint. Thus, for every set
, no matter its size, there is a function
that agrees with
on at least a
fraction of inputs from
. The reason is that the sets of inputs on which the functions of
differ from
form a partition of
, and so their intersections with
form a partition of
. By an averaging argument, one of those intersections must then contain at most
elements of
.
In the above example, however, if we choose any three distinct functions from
, we have
So, although is weakly hard on average with respect to
, we have that
is not even worst-case hard for a slight extension of
in which we allow functions obtained by simple compositions of a small number of functions of
.
Theorem 1 (Impagliazzo Hard-Core Lemma) Let
be a collection of functions
, let
a function, and let
and
be positive reals. Then at least one of the following conditions is true:
- (
is not weakly hard-on-average over
with respect to a slight extension of
) There is a
, an integer
, and
functions
, such that
satisfies
- (
is strongly hard-on-average over a set
of density
) There is a set
such that
and
Where is equal to
or
depending on whether the boolean expression is true or false (the letter “
” stands for “indicator” function of the truth of the expression).
2. Proving the Lemma
Impagliazzo’s proof had polynomial in both
and
, and an alternative proof discovered by Nisan has a stronger bound on
of the order of
. The proofs of Impagliazzo and Nisan did not immediately give a set of size
(the set had size
), although this could be achieved by iterating their argument. An idea of Holenstein allows to prove the above statement in a more direct way.
Today we will see how to obtain the Impagliazzo Hard-Core Lemma from online optimization, as done by Barak, Hardt and Kale. Their proof achieves all the parameters claimed above, once combined with Holenstein’s ideas.