## 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.