### Toda's theorem in bounded arithmetic with parity quantifiers and bounded depth proof systems with parity gates

Kolodziejczyk, L *(Uniwersytet Warszawski)*

Thursday 29 March 2012, 11:00-11:30

Seminar Room 1, Newton Institute

#### Abstract

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.

#### Presentation

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

## Comments

Start the discussion!