Algorithms versus Circuit Lower Bounds

by Igor Oliveira

Oded's comments

In quite a coincidence with the posting of Gil Cohen's Lecture Notes, I wish to call attention also to the current (advanced) survey. Here Williams' results are viewed as a special case of a general paradigm of deriving circuit lower bounds via "transference theorem" that applied to suitable nontrivial algorithms yield circuit lower bounds. This paradigm is stated in general terms, covering several results that are typically not viewed in these terms.

A relatively minor comment: In the second paragraph of Sec 1.1.3, Igor refers to my work "In a World of P=BPP" as providing "evidence that pseudorandom generators are necessary in order to derandomize probabilistic algorithms ... P=BPP". My own view is different: I think my works shows that in quite a couple of natural senses pseudorandom generators are necessary in order to derandomize probabilistic algorithms. That is, I don't view my result as evidence to something, but rather as establishing this thing in some natural sense.

The original abstract

Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability algorithms. We also cover the connection between circuit lower bounds and useful properties, a notion that turns out to be fundamental in the context of these transference theorems. Along the way, we obtain a few new results, simplify several proofs, and show connections involving different frameworks. We hope that our presentation will serve as a self-contained introduction for those interested in pursuing research in this area.

See ECCC TR13-117.

Back to list of Oded's choices.