You are not logged in |
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.
- 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.
