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.