Proof Complexity of Pigeonhole Principles

1. Urquhart, A.: The complexity of propositional proofs. Bulletin of Symbolic Logic 1 (1995) 425–467

   Article  MATH  MathSciNet  Google Scholar 

2. Krajíček, J.: Bounded arithmetic, propositional logic and complexity theory. Cambridge University Press (1995)

   Google Scholar 

3. Razborov, A.: Lower bounds for propositional proofs and independence results in Bounded Arithmetic. In auf der Heide, F.M., Monien, B., eds.: Proceedings of the 23rd ICALP, Lecture Notes in Computer Science, 1099, NewYork/Berlin, Springer-Verlag (1996) 48–62

   Google Scholar 

4. Beame, P., Pitassi, T.: Propositional proof complexity: Past, present and future. Technical Report TR98-067, Electronic Colloquium on Computational Complexity (1998)

   Google Scholar 

5. Pudlák, P.: The lengths of proofs. In Buss, S., ed.: Handbook of Proof Theory. Elsevier (1998) 547–637

   Google Scholar 

6. Cook, S.A., Reckhow, A.R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44 (1979) 36–50

   Article  MATH  MathSciNet  Google Scholar 

7. Reckhow, R.A.: On the lengths of proofs in the propositional calculus. Technical Report 87, University of Toronto (1976)

   Google Scholar 

8. Maciel, A., Pitassi, T., Woods, A.: A new proof of the weak pigeonhole principle. Manuscript (1999)

   Google Scholar 

9. Håstad, J.: Computational limitations on Small Depth Circuits. PhD thesis, Massachusetts Institute of Technology (1986)

   Google Scholar 

10. Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the 28th ACM STOC. (1996) 174–183

    Google Scholar 

11. Ben-Sasson, E., Wigderson, A.: Short proofs are narrow — resolution made simple. In: Proceedings of the 31st ACM STOC. (1999) 517–526

    Google Scholar 

12. Alekhnovich, M., Ben-Sasson, E., Razborov, A., Wigderson, A.: Pseudorandom generators in propositional complexity. In: Proceedings of the 41st IEEE FOCS. (2000) 43–53

    Google Scholar 

13. Razborov, A.: Improved resolution lower bounds for the weak pigeonhole principle. Technical Report TR01-055, Electronic Colloquium on Computational Complexity (2001)Available at ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2001/TR01-055/index.html.

14. Haken, A.: The intractability or resolution. Theoretical Computer Science 39 (1985) 297–308

    Article  MATH  MathSciNet  Google Scholar 

15. Buss, S.R.: Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic 52 (1987) 916–927

    Article  MATH  MathSciNet  Google Scholar 

16. Cook, W., Coullard, C.R., Turán, G.: On the complexity of cutting plane proofs. Discrete Applied Mathematics 18 (1987) 25–38

    Article  MATH  MathSciNet  Google Scholar 

17. Ajtai, M.: The complexity of the pigeonhole principle. In: Proceedings of the 29th IEEE Symposium on Foundations of Computer Science. (1988) 346–355

    Google Scholar 

18. Bellantoni, S., Pitassi, T., Urquhart, A.: Approximation of small depth Frege proofs. SIAM Journal on Computing 21 (1992) 1161–1179

    Article  MATH  MathSciNet  Google Scholar 

19. Pitassi, T., Beame, P., Impagliazzo, R.: Exponential lower bounds for the pigeonhole principle. Computational Complexity 3 (1993) 97–140

    Article  MATH  MathSciNet  Google Scholar 

20. Krajíček, J., Pudlák, P., Woods, A.R.: Exponential lower bounds to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures and Algorithms 7 (1995) 15–39

    Article  MathSciNet  MATH  Google Scholar 

21. Razborov, A.: Lower bounds for the polynomial calculus. Computational Complexity 7 (1998) 291–324

    Article  MATH  MathSciNet  Google Scholar 

22. Impagliazzo, R., Pudlák, P., Sgall, J.: Lower bounds for the polynomial calculus and the Groebner basis algorithm. Computational Complexity 8 (1999) 127–144

    Article  MATH  MathSciNet  Google Scholar 

23. Alekhnovich, M., Razborov, A.: Lower bounds for the polynomial calculus: non-binomial case. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. (2001) 190–199

    Google Scholar 

24. Riis, S.: Independence in Bounded Arithmetic. PhD thesis, Oxford University (1993)

    Google Scholar 

25. Paris, J.B., Wilkie, A.J., Woods, A.R.: Provability of the pigeonhole principle and the existence of infinitely many primes. Journal of Symbolic Logic 53 (1988) 1235–1244

    Article  MATH  MathSciNet  Google Scholar 

26. Krajíček, J.: On the weak pigeonhole principle. Fundamenta Mathematicae 170 (2001) 123–140

    Article  MathSciNet  MATH  Google Scholar 

27. Buss, S., Turán, G.: Resolution proofs of generalized pigeonhole principle. Theoretical Computer Science 62 (1988) 311–317

    Article  MATH  MathSciNet  Google Scholar 

28. Atserias, A.: Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms. In J. Sgall, A. Pultr, P.K., ed.: Proceedings of the 26th International Symposium on the Mathematical Foundations of Computer Science (Marianske Lazne, August’ 01), Lecture Notes in Computer Science 2136, Springer-Verlag (2001) 148–158

    Google Scholar 

29. Atserias, A., Bonet, M.L., Esteban, J.L.: Lower bounds for the weak pigeonhole principle beyond resolution. To appear in Information and Computation (2000)

    Google Scholar 

30. Buss, S., Pitassi, T.: Resolution and the weak pigeonhole principle. In: Proceedings of the CSL97, Lecture Notes in Computer Science, 1414, NewYork/Berlin, Springer-Verlag (1997) 149–156

    Google Scholar 

31. Razborov, A., Wigderson, A., Yao, A.: Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. In: Proceedings of the 29th ACM Symposium on Theory of Computing. (1997) 739–748

    Google Scholar 

32. Pitassi, T., Raz, R.: Regular resolution lower bounds for the weak pigeonhole principle. In: Proceedings of the 33rd ACM Symposium on the Theory of Computing. (2001) 347–355

    Google Scholar 

33. Raz, R.: Resolution lower bounds for the weak pigeonhole principle. Technical Report TR01-021, Electronic Colloquium on Computational Complexity (2001)

    Google Scholar 

34. Razborov, A.: Resolution lower bounds for the weak functional pigeonhole principle. Manuscript, available at http://www.mi.ras.ru/~razborov/matching.ps (2001)

35. Razborov, A.: Resolution lower bounds for perfect matching principles. Manuscript, available at http://www.mi.ras.ru/~razborov/matching.ps (2001)

36. Razborov, A.: Bounded Arithmetic and lower bounds in Boolean complexity. In Clote, P., Remmel, J., eds.: Feasible Mathematics II. Progress in Computer Science and Applied Logic, vol. 13. Birkhäuser (1995) 344–386

    Google Scholar 

37. Dantchev, S., Riis, S.: “Planar” tautologies hard for Resolution. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. (2001) 220–229

    Google Scholar 

38. Alekhnovich, M.: Mutilated chessboard is exponentially hard for resolution. Manuscript (2000)

    Google Scholar 

39. Beame, P., Riis, S.: More on the relative strength of counting principles. In Beame, P., Buss, S., eds.: Proof Complexity and Feasible Arithmetics: DIMACS workshop, April 21–24, 1996, DIMACS Series in Dicrete Mathematics and Theoretical Computer Science, vol. 39. American Math. Soc. (1997) 13–35

    Google Scholar 

Download references