Propositional Proofs in Frege and Extended Frege Systems (Abstract)
Proc., 10th International Computer Science Symposium in Russia (CSR)
Lecture Notes in Computer Science 9139
Springer-Verlag, 2015, p. 1-6.
Download manuscript: PDF.
Abstract: We discuss recent results on the propositional proof complexity of Frege proof systems, including some recently discovered quasipolynomial size proofs for the pigeonhole principle and the Kneser-Lov\'asz theorem. These are closely related to formalizability in bounded arithmetic.
Back to Sam Buss's publications page.