The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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


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.


[pdf ]


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.

Back to top ∧