[Proof Complexity] Paper available (Quasipoly size Frege proofs of PHP)

[Sam Buss]

Dear colleagues,

I have posted a new preprint, "Quasipolynomial Size Proofs of the
Propositional Pigeonhole Principle", available from
http://www.math.ucsd.edu/~sbuss/ResearchWeb/QuasiPolyPHP/.  (The direct link
to the PDF is
http://www.math.ucsd.edu/~sbuss/ResearchWeb/QuasiPolyPHP/paper.pdf.)

Comments, suggestions, corrections are appreciated.

Best regards, Sam

====
Abstract: Cook and Reckhow proved in 1979 that the propositional pigeonhole
principle has polynomial size extended Frege proofs. Buss proved in 1987
that it also has polynomial size Frege proofs; these Frege proofs used a
completely different proof method based on counting. This paper shows that
the original Cook and Reckhow extended Frege proofs can be formulated as
quasipolynomial size Frege proofs. The key point is that st-connectivity can
be used instead of counting.