How Complex Is Complexity? Or What’s a ‘Meta’ for? | Richard M. Karp Distinguished Lecture

Abstract: 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.

=========================================================

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience. Light refreshments will be available prior to the start of the lecture. This lecture will be viewable thereafter on this page and on our YouTube channel.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.