CMSC 39600-1: Propositional Proof Complexity (Topics in Theoretical Computer Science)

Course description

Winter09: Tuesday, Thursday 4:30pm-5:50pm (Ry 276)


  1. N. Segerlind, The complexity of propositional proofs, The Bulletin of Symbolic Logic, volume 13, number 4, pages 482-537, 2007.
  2. P. Beame, T. Pitassi, Propositional proof complexity: Past, present, and future, Current trends in theoretical computer science: Entering the 21st century , World Scientific Publishing, 2001, pp. 42–70. Available at Beame's home page.
  3. P. Beame, Proof complexity, Computational Complexity Theory, volume 10 of IAS/Park City mathematics series, pages 199-246. American Mathematical Society, 2004. Available at Beame's home page.
  4. E. Ben-Sasson, A. Wigderson, Short Proofs Are Narrow—Resolution Made Simple, Journal of the ACM, Vol. 48, No. 2, March 2001, pp. 149 –169.
  5. J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen and T. Pitassi, Rank Bounds and Integrality Gaps for Cutting Planes Procedures, Theory of Computing, volume 2, 2006, pp. 65-90.
  6. S. Arora, B. Bollobas, L. Lovasz, I. Tourlakis, Proving integrality gaps without knowing the linear program, Theory of Computing, Vol. 2, p. 19-51, 2006
  7. M. Alekhnovich, M. Braverman, V. Feldman, A. R. Klivans, T. Pitassi, Learnability and automatizability, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pages 621 - 630.
  8. S. Buss, Bounded Arithmetic, Napoli : Bibliopolis, 1986, 221 p. Available at Buss's home page.
  9. J. Krajicek, Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, 1995.
  10. P. Hajek, P. Pudlak, Metamathematics of first-order arithmetic, Springer-Verlag, 1993.
  11. G. Takeuti, RSUV isomorphism, Arithmetic, Proof Theory and Computational Complexity, eds. P. Clote and J. Krajicek, Oxford University Press, 1993, pages 364-386
  12. A. Razborov, An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic, Arithmetic, Proof Theory and Computational Complexity, eds. P. Clote and J. Krajicek, Oxford University Press, 1993, pages 247-277
  13. F. Ferreira, Polynomial time computable arithmetic and conservative extensions, Ph.D., The Pennsylvania State University, 1988, 176 pages
  14. J. Krajícek, P. Pudlak, G. Takeuti, Bounded Arithmetic and the Polynomial Hierarchy, Ann. Pure Appl. Logic, 1991, 52(1-2): 143-153
  15. S. Buss, J. Krajicek, An application of Boolean complexity to separation problems in Bounded arithmetic, Proceedings of the London Mathematical Society, 69(1994), pages 1-21
  16. A. Beckmann, S. Buss, Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic, 2008, preprint downloadable from Buss's home page
  17. A. Razborov, Proof Complexity of Pigeonhole Principles, in Proceedings of the 5th Developments in Language Theory Conference, Lecture Notes in Computer Science, vol. 2295, 2002, pages 100-116.
  18. P. Pudlak, Twelve problems in proof complexity, Proc. 3rd International Computer Science Symposyum in Russia, CSR 2008, LNCS 5010, pp.13-27.
  19. S. Buss, Bounded Arithmetic and Propositional Proof Complexity, in Logic of Computation, edited by H. Schwichtenberg. Springer-Verlag, Berlin, 1997, pp. 67-122.
  20. A. Razborov, On Provably Disjoint NP-pairs, Basic Research in Computer Science Center, 1994.
  21. J. Krajicek, P. Pudlak, Some consequences of cryptographical conjectures for S_2^1 and EF, Information and Computation, vol. 140 (1998), no. 1, pp. 82-94.
  22. M. Alekhnovich, A. Razborov, Resolution Is Not Automatizable Unless W[P] Is Tractable, SIAM J. Comput. 38(4): 1347-1363 (2008)
  23. M. Alekhnovich, M. Braverman, V. Feldman, A. Klivans, T. Pitassi, The complexity of properly learning simple concept classes, J. Comput. Syst. Sci., 74(1): 16-34 (2008).
  24. M. Alekhnovich, A. Razborov, Satisfiability, Branch-Width and Tseitin Tautologies, Proc. of the 43rd IEEE FOCS, 2002, pages 593-603.
  25. K. Eickmeyer, M. Grohe, M. Grüber, Approximation of natural W[P]-complete minimisation problems is hard, Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC'08), pp.8-18, 2008.
  26. P. Beame, S. Riis, More on the relative strength of counting principles, In Paul W. Beame and Samuel R. Buss, editors, Proof Complexity and Feasible Arithmetics, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 13-35. American Mathematical Society, 1998.
  27. D. Grigoriev, E. Hirsch, D.Pasechnik, Complexity of semi-algebraic proofs, Moscow Mathematical Journal, 2(4): 647-679, 2002.
  28. Bonet, M., Pitassi, T. and Raz, R., Lower bounds for Cutting Planes proofs with small coefficients, Journal of Symbolic Logic, Vol. 62, No. 3, pp. 708-728, 1997.
  29. P. Pudlak, Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic, 62(3), 1997, pp.981-998.
  30. J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, T. Pitassi, Rank Bounds and Integrality Gaps for Cutting Planes Procedures, Theory of Computing, Volume 2 (2006), Article 4, pp. 65-90.
  31. A. Razborov, Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution, manuscript. Available at my home page.
  32. A. Razborov, Resolution Lower Bounds for Perfect Matching Principles, Journal of Computer and System Sciences, Vol. 69, No 1, 2004, pages 3-27.
  33. M. Alekhnovich, E. Ben-Sasson, A. Razborov, A. Wigderson, Pseudorandom Generators in Propositional Proof Complexity, SIAM Journal on Computing, Vol. 34, No 1, 2004, pages 67-88.
  34. J. Krajicek, Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, J. of Symbolic Logic, 69(1), (2004), pp.265-286.