$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem
Lance Fortnow
cs.CC
2026-09-28
Fortnow builds a poly-seed PRG from exponential F2-polynomial correlation bounds, proving Almost-⊕P = BP·⊕P and derandomizing the random-oracle half of Toda.
Complexity theory has a line of results that turn truth for almost every oracle into a bounded-error class. Bennett and Gill showed Almost-P = BPP: a language that sits in P relative to a random oracle, with probability one, is already in BPP. Nisan and Wigderson did the same for the polynomial hierarchy, Almost-PH = PH. The parity analogue was missing.
⊕P is the parity version of NP. A nondeterministic polynomial-time machine accepts iff the number of accepting paths is odd. Almost-⊕P collects languages that land in ⊕P^R with probability one for a random oracle R. BP·⊕P is the class obtained by a bounded-error randomized reduction to ⊕P. The question is whether those two coincide.
The first half of Toda's theorem is PH ⊆ BP·⊕P: the whole polynomial hierarchy randomly reduces to one parity count. Regan and Royer wanted to prove it by collapsing PH into ⊕P under a random oracle, then removing the oracle. The abstract says that route was incomplete. The missing piece, as stated, is a pseudorandom generator with polynomial seed length that fools F2-polynomials of polynomial degree on exponentially many variables. Without it, parity computations relative to a random oracle do not compress back to short randomness.
The engine is an exponential correlation bound of Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola. Correlation here measures how close two Boolean functions are: F2-polynomials on one side, the XOR of majority functions on the other. Exponentially small correlation means a low-degree polynomial cannot tell that XOR-of-majorities function from a random string. A generator with a short seed that expands into a long string then fools every polynomial-degree F2-polynomial.
The abstract only states the generator qualitatively: polynomial seed, exponentially many variables, polynomial degree. A random oracle is an exponentially large truth table. A ⊕P machine makes only polynomially many queries, but to simulate a probability-one statement over that oracle the generator has to fool low-degree polynomials on exponentially many coordinates at once. The seed still has to be polynomial, or it will not fit in the BP operator. Queries of a ⊕P machine to a random oracle often look like such polynomials. Replacing the oracle with the generator leaves a short seed, which belongs in the BP operator, so Almost-⊕P falls into BP·⊕P. The reverse inclusion for Almost classes usually follows from the definition; the abstract does not spell it out.
The Toda application follows Regan and Royer. Relative to a random oracle, each level of PH is hit with Valiant-Vazirani, which randomly reduces SAT to a formula with at most one solution and thereby peels off an NP quantifier. Then Papadimitriou-Zachos gives ⊕P^⊕P = ⊕P. Doing this level by level puts PH inside ⊕P relative to a random oracle, and no probabilistic quantifier is ever moved through the oracle. That yields PH ⊆ Almost-⊕P. The main theorem strips the oracle and leaves PH ⊆ BP·⊕P in the unrelativized world.
The abstract compares this argument with Fortnow's 2009 short proof of Toda's theorem. The comparison itself is in the full text, which was not retrieved.
This is a proof paper. The abstract gives no experimental numbers and no concrete seed degree or error bound.
| Claim | Statement | Comparison |
| Main theorem | Almost-⊕P = BP·⊕P | Bennett-Gill Almost-P = BPP; Nisan-Wigderson Almost-PH = PH |
| Tool | Polynomial-seed PRG fooling polynomial-degree F2-polynomials on exponentially many variables | Correlation bounds of Chattopadhyay et al. |
| Toda, first half | PH ⊆ BP·⊕P | Collapse into ⊕P under a random oracle, then remove the oracle |
| Proof constraint | No probabilistic quantifier is moved through an oracle | Differs from common relativizing writeups |
Exact polynomial degree of the seed, the exponential base of the correlation bound, and how error transfers into the PRG are not in the abstract. Those details sit in the missing full text.
For people working on complexity, derandomization, or counting classes, this fills the Almost slot for ⊕P. Toda's statement is old. The path is new: collapse under a random oracle level by level, then remove the oracle with an F2-polynomial PRG, never sliding a BP quantifier through an oracle query.
Nobody should expect a runnable algorithm or a change to a training stack. If you already read Toda reductions, Valiant-Vazirani isolation, or pseudorandomness for F2-polynomials, the chain from correlation bounds to a PRG to oracle removal is now complete. Otherwise the 2009 short proof remains the shorter way to learn Toda. The abstract puts the two proofs side by side; the point of the comparison is structure, not length.
The full paper was not retrieved. The polynomial degree of the seed, the base of the exponential correlation bound, PRG error, and the degree window the generator actually fools cannot be checked. The second half of Toda, BP·⊕P ⊆ P^{#P}, is out of scope.
The phrase complete a random-oracle proof means the Regan-Royer route was missing the oracle-removal step. Which lemma was missing is not in the abstract. Whether the new proof assumes a stronger circuit lower bound than the 2009 argument is also in the full text. The correlation bound is used as a black box. If that bound depends badly on degree or on the number of variables, the PRG may only work in a restricted polynomial window, and the abstract does not state that window.