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.

Back to Sam Buss's publications page.