##
Non-trivial derandomization implies weak lower bounds:
An exposition of an (almost) elementary proof

by Roei Tell

#### Oded's comments

This three-page text (+ a page of references) provides an exposition
to the core of Ryan's breakthrough result
that yields a relatively explicit function (i.e., one in NEXT) not in ACC.
The exposition focuses on the derivation of a lower bound
for a circuit class *C*
based on an extremely weak (but non-trivial) derandomizations
for (a circuit class that is closely related to) *C*.

This is a good opportunity to commend Roei for making
(polished versions of) his self-teaching notes availble to others
at https://sites.google.com/site/roeitell/Expositions.

#### The original abstract

Ryan Williams' fundamental result asserts that any non-trivial derandomization
of a circuit class C implies weak lower bounds for C. This text presents an
alternative (known) argument, in which C is separated from the class E^{NP}
(rather than from the class NEXP, as in the original result). The proof is
short, almost completely self-contained, and applies to more classes C than
the original result.

See Roei's
expositions page.

Back to
list of Oded's choices.