Eric Allender, Rutgers University

Abstract

The Minimum Circuit Size Problem (MCSP) has been a central problem in the study of computational complexity theory for a long time, and it promises to remain a focus of attention for many years to come. This problem can be said to capture the question of whether it is difficult to prove lower bounds; it appears to be hard, but is it really? This talk will touch on the rich connections between MCSP and other topics in theoretical computer science, and will survey some of the remarkable recent progress that has been made.

Speaker Bio: Eric Allender is Distinguished Professor of Computer Science at Rutgers University. His research centers on questions in complexity theory, including circuit complexity, Kolmogorov complexity, resource-bounded measure theory, and properties of complexity classes. Allender is a Fellow of the Association of Computing Machinery (ACM) and a 2009-2010 recipient of a Fulbright research fellowship. He has regularly served on the DIMACS Executive Committee and Council, been a frequent and popular REU mentor, was co-organizer of the DIMACS Special Year on Logic and Algorithms, and is currently co-organizer for the Special Focus on Lower Bounds in Computational Complexity.

Slides  Video