Metraipolis › archive › dc_bcf493222e92
$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem — arXiv:2609.35326
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35326
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:43:22.672Z
- SHA-256 of the archived text
16ce984aa4b8a04f211d4961e0f18eafc2b0f2dddf48d9d005550cc0a1a78d1d- Stable URL of this page
https://metraipolis.com/documento/dc_bcf493222e92
How to cite
$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem — arXiv:2609.35326 — arXiv (en), https://arxiv.org/abs/2609.35326 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bcf493222e92 (Metraipolis archive dc_bcf493222e92, sha256 16ce984aa4b8a04f211d4961e0f18eafc2b0f2dddf48d9d005550cc0a1a78d1d)
BibTeX
@misc{dcbcf493222e92,
title = {$mathrmAlmosttext-oplusmathrmP = mathrmBPcdotoplusmathrmP$ and a Random-Oracle Proof of Toda's Theorem — arXiv:2609.35326},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35326},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bcf493222e92; sha256 16ce984aa4b8a04f211d4961e0f18eafc2b0f2dddf48d9d005550cc0a1a78d1d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35326. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that $\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$, where $\mathrm{Almost}\text{-}\oplus\mathrm{P}$ is the class of languages that lie in $\oplus\mathrm{P}^R$ with probability one for a random oracle $R$. This is the parity analogue of Bennett and Gill's $\mathrm{Almost}\text{-}\mathrm{P} = \mathrm{BPP}$ and Nisan and Wigderson's $\mathrm{Almost}\text{-}\mathrm{PH} = \mathrm{PH}$. The key ingredient is a pseudorandom generator with polynomial seed length that fools $\mathbb{F}_2$-polynomials of polynomial degree on exponentially many variables. As an application we complete a random-oracle proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P}$, following an approach of Regan and Royer. Relative to a random oracle, the polynomial hierarchy collapses into $\oplus\mathrm{P}$ by applying Valiant-Vazirani and Papadimitriou-Zachos level by level, with no probabilistic quantifier ever moved through an oracle. Our result then removes the oracle. We compare this argument with the simple proof of Toda's theorem by Fortnow (2009).
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.35326 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T00:17:42.554Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).