# Open No More

> Source: <https://blog.computationalcomplexity.org/2026/10/open-no-more.html>
> Published: 2026-10-07 15:42:22+00:00

I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a [treasure trove](https://github.com/openai/math/blob/main/overview.pdf) of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:

Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Avishay Tal [posted a paper](https://arxiv.org/abs/2609.25680) 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](https://arxiv.org/abs/2604.11952) 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](https://bibbase.org/network/publication/fortnow-complexitytheoreticaspectsofinteractiveproofsystems-1989)." $\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}$](https://link.springer.com/article/10.1007/BF01200056) 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](https://arxiv.org/abs/2609.28839). 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](https://doi.org/10.1007/BF01303057) 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](https://arxiv.org/abs/2609.35326).

I still have many more open problems, see for example [my survey of open oracle questions](https://dl.acm.org/doi/10.1145/3494656.3494663). 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.