Abstract: Computational complexity theory is rooted in many of computer science's most fascinating questions. Three examples of such questions are: Are there functions that are simple to describe, and yet require large circuits to compute? Are there short mathematical theorems that require lengthy proofs? Does every efficient randomized algorithm have an efficient deterministic counterpart?
In this talk I will describe results motivated by and contributing to our understanding of these questions, focusing on three results:
(1) An average-case depth hierarchy theorem for boolean circuits, which resolves a thirty-year-old conjecture in circuit complexity;
(2) Exponentially-improved lower bounds for the Frege proof system, the canonical proof system for propositional logic;
(3) The fastest deterministic algorithm for finding satisfying assignments of CNF formulas that have many such assignments, a basic unresolved problem in derandomization.
These results highlight rich connections among the respective subfields of complexity theory --- circuit complexity, proof complexity, and pseudorandomness --- and also have implications to areas outside of complexity theory, such as parallel computing and SAT solving. I will also touch on how the techniques we have developed point to avenues for progress on a few flagship challenges of complexity theory.
Bio: Li-Yang Tan received a PhD in Computer Science from Columbia University in 2014. From 2014 to 2015 he was a Microsoft Research fellow at the UC Berkeley Simons Institute for the Theory of Computing, and since 2015 he has been a research assistant professor at the Toyota Technological Institute in Chicago. His research interests are in computational complexity, with an emphasis on circuit complexity, proof complexity, pseudorandomness, and the analysis of boolean functions. He is a recipient of the Best Paper award at FOCS '15 and an NSF Algorithmic Foundations (Medium) award.
Host: Costis Daskalakis