Complexity in Oxford

Oxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a wonderful workshop this past week. It's my first trip to Oxford since I came five years ago to celebrate the opening of the Andrew Wiles building, a building that hosted this weeks' workshop as well.

We also got a chance to see old math and physics texts. Here's Euclid's algorithm from an old printing of Euclid's Elements.

Unlike a research conference, this workshop had several talks that gave a broader overview of several directions in complexity with a different theme each day.

A few highlights of the many great talks.

Sasha Razborov gave a nice discussion of proof systems that help us understand what makes circuit bounds hard to prove.

Tuesday was a day for pseudorandomness, finding simple distributions that certain structure can't distinguish from random. Ryan O'Donnell talked about fooling polytopes (ANDs of weighted threshold functions). Avishay Tal talked about his new oracle with Ran Raz, viewing it in this lens as a distribution that the low-depth circuit can't distinguish but quantum can. I talked about some simple extensions to Raz-Tal and the possibilities of using their techniques to show that you can't pull out quantumness in relativized worlds.

Toni Pitassi talked about lifting--creating a tight connection between decision tree and 

complexity bounds to export lower bounds from one model to the other. Yuval Ishai talked about the continued symbiosis between complexity and theoretical cryptography.

Ryan Williams talked about his approach of using circuit satisfiability algorithms to prove lower bounds that led to his famed NEXP not in ACC⁰ result. He has had considerable recent progress including his recent work with Cody Murray getting reducing NEXP to nondeterministic quasipolynomial time.

Great to get away and just think complexity for a week. Seeing my former students Rahul Santhanam and Josh Grochow all grown up. And realizing I've become that old professor who regales (or bores) telling complexity stories from long ago.