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

Prelegent(ci)

Leszek Kołodziejczyk

Afiliacja

Uniwersytet Warszawski

Termin

23 stycznia 2013 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---