Parity complexity classes shown equivalent using random oracles

$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem

Computational Complexity

Summary

This paper explores a deep question in theoretical computer science about how certain complexity classes, which categorize problems based on how hard they are to solve, relate to each other when randomness is involved. The authors use recent mathematical results about polynomials to prove that two complexity classes involving parity computations are equal when considering random oracles. They also provide a new proof related to Toda's theorem, which explains how problems in a complex hierarchy can be solved using a class related to counting solutions modulo two. This work clarifies the power of randomness and parity in computational complexity.

What this means in practice

  • For complexity theorists: Clarify relationships between complexity classes involving randomization and parity computations to guide theoretical research.
  • For cryptography engineers: Use improved pseudorandom generators that fool certain polynomial computations as building blocks in cryptographic constructions.

A theory result. No direct application yet.

Authors

Lance Fortnow

Abstract

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).
View PDFOpen arXiv