Seminar

Registration required to attend or view on Zoom

The fundamental open questions in complexity theory have resisted our best efforts for more than half a century. But is there any reason to believe that it is fundamentally difficult to show that certain problems are hard to compute? In other words, what is the computational complexity of computational complexity? This question lies at the core of the study of meta-complexity, which is the focus of the Simons Institute this semester. This lecture will survey a few highlights this study has revealed thus far, and show how meta-complexity has opened up some promising new avenues of attack on the long-standing open questions of computational complexity theory.

Eric Allender is widely recognized as a leading researcher in computational complexity theory. His research frequently exploits connections between computational complexity and Kolmogorov complexity — the study of how “random’ an object is. He has given numerous invited addresses at computer science symposia worldwide. He received a BA from the University of Iowa in 1979, majoring in computer science and theater, and a PhD from Georgia Tech in 1985. He has been at Rutgers University since then, rising to the rank of distinguished professor, and serving as department chair from 2006 to 2009. He is a fellow of the ACM, has served frequently on conference program committees, and has held various offices in SIGACT and the Computational Complexity Foundation. During the 2009/2010 academic year, he was a Fulbright fellow in South Africa.