Fortnow proves Almost-ParityP = BP·ParityP, yielding a random-oracle proof of Toda's theorem
fortnow · x · 2026-09-29
Complexity theorist Lance Fortnow posted a 6-page arXiv paper showing Almost-ParityP = BP·ParityP, using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between F₂-polynomials and the XOR of majorities.
- The result is the parity analogue of Bennett-Gill's Almost-P = BPP and Nisan-Wigderson's Almost-PH = PH.
- Key ingredient: a pseudorandom generator with polynomial seed length that fools polynomial-degree F₂-polynomials over exponentially many variables.
- As an application, it completes a random-oracle proof of the first half of Toda's theorem (PH ⊆ BP·⊕P), following Regan-Royer: the polynomial hierarchy collapses to ⊕P relative to a random oracle via Valiant-Vazirani and Papadimitriou-Zachos applied level by level, then the oracle is removed.
More from Research
- Google Cloud reproduces Olmo 3 7B pre-training on TPUs, matching Ai2 on held-out evals — allen_ai · 2026-09-29
- Researcher builds JevBench, a new 3,604-question evaluation benchmark pool — airesearch12 · 2026-09-29
- Microsoft Research unveils Project Quine, an AI research system combining biology world model with wet lab — erichorvitz · 2026-09-29
- Stanford's Kundaje Lab ports Illumina's PromoterAI to PyTorch, validates TERT promoter mutation scores — anshulkundaje · 2026-09-29
- Why Living Science Still Matters in the AI Era: Three Arguments — ChenhaoTan · 2026-09-29
- AI Revisits Cengiz et al.: 236 Minimum Wage Hikes Show No Detectable Job Loss — ChenhaoTan · 2026-09-29