Toda's theorem in bounded arithmetic with parity quantifiers and bounded depth proof systems with parity gates
Seminar Room 1, Newton Institute
The "first part" of Toda's theorem states that every language in the polynomial hierarchy is probabilistically reducible to a language in $\oplus P$. The result also holds for the closure of the polynomial hierarchy under a parity quantifier.
We use Jerabek's framework for approximate counting to show that this part of Toda's theorem is provable in a relatively weak fragment of bounded arithmetic with a parity quantifier. We discuss the significance of the relativized version of this result for bounded depth propositional proof systems with parity gates.
Joint work with Sam Buss and Konrad Zdanowski.