Strachey Lecture: Professor Ryan O'Donnell, Carnegie Mellon University, USA

Title: ETH false, Unique-Games true, BPL=L, and all that

Abstract:

The last half-year has seen spectacular advances in computational complexity theory, thanks to AI-developed proofs: subexponential-time 3SAT algorithms, optimal NP-hardness for basic approximate-optimization tasks, and derandomization of space-bounded algorithms. I will give a high-level tour of some of the new results, explain ideas that go into their proofs, and give some outlook for the future.

Bio:

Ryan O’Donnell is a Professor of Computer Science at Carnegie Mellon University, working in theoretical computer science and mathematics. His research spans the analysis of Boolean functions, computational complexity, spectral graph theory, and quantum computation and information. He is the author of the textbook Analysis of Boolean Functions and has made influential areas such as optimal hardness-of-approximation, quantum state tomography, and high-dimensional expanders. O’Donnell received his Ph.D. from MIT in 2003, advised by Madhu Sudan. His honors include an NSF CAREER Award, a Sloan Research Fellowship, best paper and best student paper awards at the Conference on Computational Complexity, a FOCS Test of Time Award, and an invited lecture at the 2014 International Congress of Mathematicians.

The Strachey Lectures are generously supported by OxFORD Asset Management

Description supplied by the event organiser.