COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Toda's theorem in bounded arithmetic with parity quantifiers and bounded depth proof systems with parity gates

## Toda's theorem in bounded arithmetic with parity quantifiers and bounded depth proof systems with parity gatesAdd to your list(s) Download to your calendar using vCal - Kolodziejczyk, L (Uniwersytet Warszawski)
- Thursday 29 March 2012, 11:00-11:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing 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. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsType the title of a new list here Scott Polar Research Institute - HCEP (Histories, Cultures, Environments and Politics) Research Seminars cri## Other talksThe Move of Economics Ideas and Numbers into Policy Finding the past: Medieval Coin Finds at the Fitzwilliam Museum Positive definite kernels for deterministic and stochastic approximations of (invariant) functions Calcium signalling in bipolar disorder - new twists to an old story Dynamical large deviations in glassy systems Stopping the Biological Clock – The Lazarus factor and Pulling Life back from the Edge. |