CMI Silver Jubilee Lecture
Howard Straubing, Boston College, USA
What can automata theory tell us about computational complexity?
Thursday, February 12, 2015
In the 1980's, the discovery of new methods for obtaining lower bounds on the computing power of small-depth circuits fueled hopes that solutions to the great open questions of computational complexity might be close at hand. At roughly the same time, striking connections between circuit complexity and the algebraic theory of finite automata led some of us to believe that regular languages and finite semigroups could settle the stubborn open questions about small-depth circuits that were blocking further progress. Nearly three decades later, those questions remain as stubbornly open as ever. Fundamental obstacles to the continued success of hitherto effective methods were discovered. And the algebra-automata approach, while it taught us a great deal about the circuit complexity of regular languages, only nibbled around the edges what more robust computational models could do. Still, the connections remain as fascinating as ever, and there are even a few fresh ideas out there. My talk will survey the research on these automata-complexity connections, from the hopeful beginnings to very recent developments.