There is widespread consensus that one of the most challenging and important problems in computer science is to show that certain problems cannot be computed by small circuits. This lecture will review why proving circuit size lower bounds is so important (and will also review the relationship between this problem and the P vs NP problem), and will also discuss some of the reasons why there is such widespread pessimism about the likelihood of proving superpolynomial circuit size lower bounds any time in the near future. We will also present some recent developments that suggest that there might be reason to be more hopeful about the prospects for proving lower bounds.
Eric Allender is widely recognized as a leading researcher in computational complexity theory. He has given numerous invited addresses at computer science symposia worldwide. He is a Fellow of the ACM, and is a distinguished professor at Rutgers University, the State University of New Jersey, where he served as department chair from 2006 to 2009. He serves on the editorial boards of ACM Transactions on Computation Theory, Computational Complexity, and The Chicago Journal of Theoretical Computer Science.
He is visiting South Africa as a Fulbright Fellow, and will be at UCT through December, 2009.