Next: About this document ...
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)
- Beame's note on resolution.
- Resolution and the weak pigeonhole principle by Buss and Pitassi.
- Improved resolution lower bounds for the weak pigeonhole principle
by Razborov. 2001.
Notes on Razborov's result on many pigeons by Jukna.
- Resolution lower bounds for the weak functional pigeonhole principle
by Razborov. 2003.
- The complexity of propositional proofs by Nathan Segerlind.
- Read once programs, rectangular proofs of the pigeonhold principle
and the traversal calculus by Razborov, Wigderson, Yao. 2002.
- A lower bound for the pigeonhold principle in tree-resolution by
asymmetric prover-delayer games by Beyerdorff, Galesi, Lauria.
My talk on it: mytalk.pdf.
- A note on propositional proof complexity of some Ramsey
type statements by Krajicek. 2010.