DIMACS TR: 97-49
Circuit Complexity before the Dawn of the New Millennium
Author: Eric Allender
ABSTRACT
The 1980's saw rapid and exciting development of techniques for proving
lower bounds in circuit complexity. This pace has slowed recently,
and there has even been work indicating that quite different proof
techniques must be employed to advance beyond the current frontier of
circuit lower bounds. Although this has engendered pessimism
in some quarters, there have in fact been many positive developments
in the past few years showing that significant progress is possible on
many fronts. This paper is a (necessarily incomplete) survey of
the state of circuit complexity as we await the dawn of the new
millennium.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-49.ps.gz
DIMACS Home Page