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.

Registration is required to attend.

What does theoretical computer science have to do with art and the movies? Alvy Ray Smith, who has done it all, tells that story. Born before computers and pixels, he has ridden the Moore’s law supernova wave all the way from the first pixels to the first digital movie, Toy Story, from Pixar, the company he cofounded. But before that, he was an oil painter in New Mexico and then took a decade-long voyage through computation theory for his PhD work and early professorhood. A cover of Scientific American brought him an early fame of sorts and a request to design the cover for the annual proceedings of the Symposium on Foundations of Computer Science. Smith’s talk for the Simons Institute will feature that FOCS cover, used for 38 years in print and three more as the proceedings went digital. He executed it with pre-digital technology but uses it to explain the central dogma that drives much of modern computer graphics. Smith spent the last 10 years writing a book called A Biography of the Pixel. His talk will reference the book, but many parts of his discussion will be UC Berkeley specific, having to do with the computation-theory crowd and its influence.