A WebPage on Upper and Lower bounds on Resolution for PHP and Ramsey

by William Gasarch

(For now this is just papers that I want to gather in one place)

*Beame's note on resolution*. Beame's Notes*Resolution and the weak pigeonhole principle*by Buss and Pitassi. 1996. BussPit*Improved resolution lower bounds for the weak pigeonhole principle*by Razborov. 2001. r.pdf.*Notes on Razborov's result on many pigeons*by Jukna. 2011. jukna.pdf*Resolution lower bounds for the weak functional pigeonhole principle*by Razborov. 2003. r.pdf*The complexity of propositional proofs*by Nathan Segerlind. 2007. Segerlind.pdf*Read once programs, rectangular proofs of the pigeonhold principle and the traversal calculus*by Razborov, Wigderson, Yao. 2002. rwy.pdf*A lower bound for the pigeonhole principle in tree-resolution by asymmetric prover-delayer games*by Beyerdorff, Galesi, Lauria. 2010. BGL.pdf My talk on it: mytalk.pdf.*A note on propositional proof complexity of some Ramsey type statements*by Krajicek. 2010. K.pdf*The strength of Ramsey theorem for coloring relatively large sets*by Carlucci, Zdanoswki, Wyszynski. RELLARGE.PDF*A lower bound on the size of resolution proofs of the Ramey theorem*by Pudlak IPL, V 112, 2012, pages 610-611. RAMSEYLB.PDF