Open No More

I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a treasure trove of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:

• A proof of the unique games conjecture (formalized in Lean)
• A full derandomization of randomized log space
• Matrix multiplication in \(n^{2.25+\epsilon}\) time (formalized in Lean)

And many many more. I had Claude put together a webpage to make it easier to explore the TCS-related results.

Now these proofs haven't been fully verified but if they hold up, we've seen more progress in theoretical computer science in the last 24 hours than in the previous three decades combined!

It will take a while to process all these results, and what it means to the field of theoretical computer science and those who work within it. Much more in future posts.

A few caveats. As incredibly impressive as this work is, AI isn't solving everything--it solved under 10% of the problems given to it. And none of these results get us any closer to settling P v NP.

Nevertheless this will be a day we will never forget. Now on to my original post of far less important results.

---

Back in January, Matt Kovacs-Deak, Daochen Wang and Rain Zimin Yang solved my open question about the decision tree complexity of rational functions. With the help of AI some of my other open questions are continuing to get solved.

Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Avishay Tal posted a paper giving an oracle where \(\mathrm{BQP}\) is not in \(\mathrm{IP}\) (interactive proofs). Now \(\mathrm{BQP}\) is in \(\mathrm{IP}\) since \(\mathrm{BQP}\subseteq\mathrm{PSPACE}=\mathrm{IP}\), but the \(\mathrm{IP}=\mathrm{PSPACE}\) proof doesn't relativize and Bouland et al. show you can even get an oracle that puts \(\mathrm{BQP}\) out of \(\mathrm{IP}\).

The paper also states "Together with recent work due to Scott Aaronson, Anand Natarajan, Avishay Tal, and Ági Villányi, our work also gives the first oracle separation between IP and MIP, answering a question dating back to Fortnow's thesis." \(\mathrm{MIP}\) is the set of languages with multi-prover interactive proofs.

When I saw this paper, I pulled my PhD thesis off the shelf and indeed on page 40 I wrote "What is the relation between MIP and IP? Is there, for instance, an oracle separating the two classes".

When I wrote the thesis in 1989 we didn't know yet that \(\mathrm{IP}=\mathrm{PSPACE}\) and \(\mathrm{MIP}=\mathrm{NEXP}\) so we really didn't have any idea whether multiple provers actually gave you more power than one prover. When László Babai, Carsten Lund and I proved \(\mathrm{MIP}=\mathrm{NEXP}\) a year later, we had strong evidence that \(\mathrm{IP}\neq\mathrm{MIP}\) since we believe that \(\mathrm{PSPACE}\neq\mathrm{NEXP}\). However since the proof that \(\mathrm{MIP}=\mathrm{NEXP}\) doesn't relativize either, the question of the oracle separation between \(\mathrm{IP}\) and \(\mathrm{MIP}\) remained open until the Bouland et al. paper.

Finally, Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal and Emanuele Viola gave new exponential correlation bounds for polynomials. The authors use that bound to give a new pseudorandom generator against \(\mathrm{AC}^0[\oplus]\) circuits.

When I saw the paper I realized one could use this generator to show that \(\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\), answering a question I had wondered about in the 90s. Here \(\text{Almost-}\oplus\mathrm{P}\) is the class of languages \(L\) such that \(L\in\oplus\mathrm{P}^R\) with probability one for a random oracle \(R\). This in turn could be used to give an alternative proof of Toda's theorem. Ken Regan and Jim Royer showed that relative to a random oracle the polynomial-time hierarchy is contained in \(\oplus\mathrm{P}\), so \(\mathrm{PH}\subseteq\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\). It would take me a long time to work out and write up the details so I had Claude do it for me.

I still have many more open problems, see for example my survey of open oracle questions. I'd be happy to see them solved. Feel free to use AI but verify the proof. You too could get mentioned on this blog.