A WebPage on Upper and Lower bounds on Resolution for PHP

by William Gasarch

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

1. Beame's note on resolution. Beame's Notes

2. Resolution and the weak pigeonhole principle by Buss and Pitassi. 1996. BussPit

3. 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

4. Resolution lower bounds for the weak functional pigeonhole principle by Razborov. 2003. r.pdf

5. The complexity of propositional proofs by Nathan Segerlind. 2007. Segerlind.pdf

6. Read once programs, rectangular proofs of the pigeonhold principle and the traversal calculus by Razborov, Wigderson, Yao. 2002. rwy.pdf

7. A lower bound for the pigeonhold principle in tree-resolution by asymmetric prover-delayer games by Beyerdorff, Galesi, Lauria. 2010. BGL.pdf My talk on it: mytalk.pdf.

8. A note on propositional proof complexity of some Ramsey type statements by Krajicek. 2010. K.pdf