## (1) Improving Exhaustive Search Implies Superpolynomial Lower Bounds

## (2) Non-Uniform ACC Circuit Lower Bounds

by Ryan Williams

#### Oded's comments

I guess the second work has already featured on all complexity theory blogs,
but still I wish to offer my own perspective on it
(as well as its predecessor, i.e., the first work).

My interest in these works arises from their high-level proof strategy,
which was introduced in the first work and bear fruits in the second.
The strategy is pivoted on showing that certain circuit lower bounds
follow from "modest" algorithmic improvements,
and in particular from improvements over exhaustive search
for some SAT-type problems.
This strategy is appealing because it seems
conceptually easier to design algorithms
(i.e,., present certain objects)
than to prove lower bounds
(i.e., demonstrate that certain objects do not exist).

Furthermore, my interest in such strategy is inherent,
because of the fact that *certain* derandomization tasks
are equivalent to *certain* circuit lower bounds.
While the common wisdom seems to be that this equivalence indicates
that these derandomization tasks are unlikely to be resolved in our
lifetime (because that's the view regarding establishing lower bounds,
in general), my current feeling
(expressed in my RANDOM'10 talk)
is that we may expect to see proofs of these specific lower bounds
(because designing algorithms is something we seem to know better,
whereas, in some sense, this what derandomization is about).
Thus, I view Ryan's success as a first (sound) indication
to the feasibility of my speculation.

Moreover, Ryan's first work has an explicit result about a specific
derandomization task that would imply specific lower bounds.
This was not the first result of the kind (see Ryan's paper),
but the derandomization task considered by Ryan requires
only a modest improvement beyond the trivial one.

Addendum (24/11/2010):
Or Meir has observed that the argument in the second paper
can be transformed to the context of derandomization.
Thus, a specific derandomization
(which is implicit in Ryan's SAT-solver)
yields the celebrated circuit lower bound
(i.e., the one that was considered hard to prove).

#### References

(1) Appears in the proceedings of STOC'10,
whereas (2) is available from
Ryan's webpage.

Back to
list of Oded's choices.