next up previous
Next: About this document ...

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)

  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 pigeonhole 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

  9. The strength of Ramsey theorem for coloring relatively large sets by Carlucci, Zdanoswki, Wyszynski. RELLARGE.PDF

  10. A lower bound on the size of resolution proofs of the Ramey theorem by Pudlak IPL, V 112, 2012, pages 610-611. RAMSEYLB.PDF

next up previous
Next: About this document ...
William Gasarch 2013-08-07