A collapse result for constant depth propositional proof systems with modular counting connectives - continuation

Speaker(s)

Leszek Kołodziejczyk

Affiliation

Uniwersytet Warszawski

Date

Jan. 23, 2013, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

In the second part of my talk, I would like to discuss in more detail some issues that were mentioned only briefly in the first part. In particular, I would like to say some more about:

- the definition of constant depth proof systems, with or without modular counting connectives,
- the correspondence between bounded arithmetic theories and constant depth proof systems,
- the proof of the base case of Toda's theorem (the so-called Valiant-Vazirani lemma), and some issues related to formalizing it in arithmetic.

---