Strachey Lecture: ''ETH false, Unique-Games true, BPL=L, and all that''
- Date & time
- –
- Speaker
- Professor Ryan O'Donnell
- Host
- Computer Science (Department)
- Series
- The Strachey Lectures in Computing Science
- Location
- University Museum of Natural History, University Museum of Natural History, Parks Road, Oxford, Oxfordshire, OX1 3PW, United Kingdom
- Organisation
- Oxford
Topics
About this talk
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 honours 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. 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-optimisation tasks, and derandomisation 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. The Strachey Lectures are generously supported by OxFORD Asset Management
Add to Calendar