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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

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

Download to your calendar using vCal

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:

Note that ex-directory lists are not shown.

Other lists

The Chadwick, Selwyn College, Unviersity of Cambridge Meeting the Challenge of Healthy Ageing in the 21st Century Average on weekdays: 9017.3707483 kWh

Other talks

Cooperation as a Laboratory of Being The “Art” and the “Easy”: Nicolò Pasquali’s Keyboard World Geometry and Generalization: The case of Grokking A Unified Framework for Change of Measure Inequalities: Applications to Generalization, Memorization and Privacy Title to be confirmed Title TBC
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity