zbMATH — the first resource for mathematics

Cracks in the defenses: Scouting out approaches on circuit lower bounds. (English) Zbl 1142.68363
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 3-10 (2008).
Summary: Razborov and Rudich identified an imposing barrier that stands in the way of progress toward the goal of proving superpolynomial lower bounds on circuit size. Their work on “natural proofs” applies to a large class of arguments that have been used in complexity theory, and shows that no such argument can prove that a problem requires circuits of superpolynomial size, even for some very restricted classes of circuits (under reasonable cryptographic assumptions).
This barrier is so daunting, that some researchers have decided to focus their attentions elsewhere. Yet the goal of proving circuit lower bounds is of such importance, that some in the community have proposed concrete strategies for surmounting the obstacle. This lecture will discuss some of these strategies, and will dwell at length on a recent approach proposed by Michal Kouck√Ĺ and the author.
For the entire collection see [Zbl 1136.68005].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI