(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).


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

Back to list of Oded's choices.