A collapse result for constant depth propositional proof systems with modular counting connectives
- Prelegent(ci)
- Leszek Kołodziejczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 16 stycznia 2013 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
A major open problem in propositional proof complexity is to obtain
strong (ideally, exponential) lower bounds for the size of proofs of
tautologies in constant depth proof systems with the usual boolean
connectives and a parity connective (or, more generally, a mod p
counting connective, where p is prime). I will say a few words about the
problem itself and then try to explain a recent joint result with Sam
Buss and Konrad Zdanowski: the depth of a constant depth proof involving
the parity connective can be reduced to 3 at the cost of a
quasipolynomial blowup in size.