Preprint:
Sam Buss
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.
DOI: 10.1007/978-3-319-20297-6_1.
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.