[1]   M. Alekhnovich, S. Arora, and I. Tourlakis: Towards strong approximability results in the Lovász-Schrijver hierarchy. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 294–303, 2005. [STOC:1060590.1060634].

[2]   S. Arora, B. Bollobás, and L. Lovász: Proving integrality gaps without knowing the linear program. In Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science, pp. 313–322, 2002. [FOCS:10.1109/SFCS.2002.1181954].

[3]   S. Arora, B. Bollobás, L. Lovász, and I. Tourlakis: Proving integrality gaps without knowing the linear program. Theory of Computing, 2(2):19–51, 2006. [ToC:v002/a002].

[4]   S. Arora, S. Rao, and U. Vazirani: Expander flows, geometric embeddings and graph partitioning. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 222–231, Chicago, IL, June 2004. [STOC:1007352.1007355].

[5]   A. Atserias, M. L. Bonet, and J. Levy: On Chvátal rank and cutting planes proofs. Technical Report TR03-041, ECCC, 2003. [ECCC:TR03-041].

[6]   E. Ben-Sasson and A. Wigderson: Short proofs are narrow – Resolution made simple. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 517–526, Atlanta, GA, May 1999. [STOC:301250.301392].

[7]    A. Bockmayr, F. Eisenbrand, M. E. Hartmann, and A. S. Schulz: On the Chvátal rank of polytopes in the 0/1 cube. Discrete Applied Mathematics, 98(1-2):21–27, October 1999. [10.1016S0166-218X(99)00156-0].

[8]   M. L. Bonet and N. Galesi: A study of proof search algorithms for Resolution and Polynomial Calculus. In Proceedings of the Fortieth Annual Symposium on Foundations of Computer Science, pp. 422–431, 1999. [FOCS:10.1109/SFFCS.1999.814614].

[9]   J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi: Rank bounds and integrality gaps for cutting planes procedures. In Proceedings of the Forty-Fourth Annual Symposium on Foundations of Computer Science, pp. 318–327, 2003. [FOCS:10.1109/SFCS.2003.1238206].

[10]   V. Chvátal: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4(4):305–337, 1973. [DiscMath:10.1016/0012-365X(73)90167-2].

[11]   V. Chvátal, W. Cook, and M. Hartmann: On cutting-plane proofs in combinatorial optimization. Linear Algebra and its Applications, 114/115:455–499, 1989. [10.10160024-3795(89)90476-X].

[12]   V. Chvátal and E. Szemerédi: Many hard examples for resolution. Journal of the ACM, 35(4):759–768, 1988. [JACM:48014.48016].

[13]   M. Clegg, J. Edmonds, and R. Impagliazzo: Using the Gröbner basis algorithm to find proofs of unsatisfiability. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 174–183, Philadelphia, PA, May 1996. [STOC:237814.237860].

[14]   W. Cook, C. R. Coullard, and G. Turán: On the complexity of cutting plane proofs. Discrete Applied Mathematics, 18:25–38, 1987. [10.10160166-218X(87)90039-4].

[15]   S. Dash: On the matrix cuts of Lovász and Schrijver and their use in Integer Programming. PhD thesis, Department of Computer Science, Rice University, March 2001.

[16]   S. Dash: An exponential lower bound on the length of some classes of branch-and-cut proofs. Mathematics of Operations Research, 30(3):678–700, 2005.

[17]   M. Davis and H. Putnam: A computing procedure for quantification theory. Journal of the ACM, 7(3):201–215, 1960. [JACM:321033.321034].

[18]   Friedrich Eisenbrand and Andreas S. Schulz: Bounds on the Chvátal rank of polytopes in the 0∕1-cube. In Proceedings of the Seventh Annual Conference on Integer Programming and Combinatorial Optimization, number 1610 in Lecture Notes in Computer Science, pp. 137–150, 1999. [IPCO:y0ruretrf6paebe1].

[19]   U. Feige and R. Krauthgamer: The probable value of Lovász-Schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345–370, 2003. [SICOMP:10.1137/S009753970240118X].

[20]   M. Goemans and L. Tunçel: When does the postive semidefiniteness constraint help in lifting procedures. Mathematics of Operations Research, 26:796–815, 2001.

[21]    M. Goemans and D. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115–1145, 1995. [JACM:227683.227684].

[22]   R. E. Gomory: Solving linear programming problems in integers. In R. Bellman and M. Hall, Jr., editors, Combinatorial Analysis, pp. 211–215, Providence, RI, 1960. Symposia in Applied Mathematics X, American Mathematical Society.

[23]   D. Grigoriev, E. A. Hirsch, and D. V. Pasechnik: Complexity of semi-algebraic proofs. In Proceedings of the Eighteenth Annual Symposium on Theoretical Aspects of Computer Science, number 2285 in Lecture Notes in Computer Science, pp. 419–430, 2002. [STACS:t7lpe5yvaphpp0j6].

[24]   D. Grigoriev, E. A. Hirsch, and D. V. Pasechnik: Exponential lower bound for static semi-algebraic proofs. In Proceedings of the Twenty-Ninth International Colloquium on Automata, Languages and Programming, number 2380 in Lecture notes in computer science, pp. 257–268, 2002. [ICALP:j2k07b37hmw2pfgw].

[25]   Martin Grötschel, László Lovász, and Alexander Schrijver: Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.

[26]   A. Haken: The intractability of resolution. Theoretical Computer Science, 39:297–305, 1985. [TCS:10.1016/0304-3975(85)90144-6].

[27]   Mark Hartmann: Cutting Planes and the Complexity of the Integer Hull. PhD thesis, Cornell University, 1988. Department of Operations Research and Industrial Engineering.

[28]   J. Håstad: Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001. [JACM:502090.502098].

[29]   E. A. Hirsch and A. Kojevnikov: Several notes on the power of Gomory-Chvátal cuts. Technical Report TR03-012, ECCC, 2003. [ECCC:TR03-012].

[30]   R. Impagliazzo, T. Pitassi, and A. Urquhart: Upper and lower bounds on tree-like cutting planes proofs. In Proceedings from Logic in Computer Science, 1994. [10.1109LICS.1994.316069].

[31]   L. G. Khachian: A polynomial time algorithm for linear programming. Doklady Akademii Nauk SSSR, n.s., 244(5):1093–1096, 1979. English translation in Soviet Math. Dokl. 20, 191–194.

[32]   B. Krishnamurthy: Short proofs for tricky formulas. Acta Informatica, 22:253–275, 1985. [ActaInf:mp65776636126242].

[33]   L. Lovász and A. Schrijver: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optimization, 1(2):166–190, 1991. [SIOPT:01/0801013].

[34]   Pavel Pudlák: Lower bounds for resolution and cutting plane proofs and monotone computations. Journal of Symbolic Logic, 62(3):981–998, September 1997.

[35]   G. Stalmark: Short resolution proofs for a sequence of tricky formulas. Acta Informatica, 33(3):277–280, 1996. [ActaInf:lhrhe2glkmgflbu1].

[36]   T. Stephen and L. Tunçel: On a representation of the matching polytope via semidefinite liftings. Mathematics of Operations Research, 24(1):1–7, 1999.

[37]   I. Tourlakis: New lower bounds for vertex cover in the Lovász-Schrijver hierarchy. Manuscript, 2005.

[38]   I. Tourlakis: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-Schrijver hierarchy. In Proceedings of Eighth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Ninth International Workshop on Randomization and Computation, pp. 233–244, 2005.

[39]   G. S. Tseitin: On the complexity of derivation in the propositional calculus. In A. O. Slisenko, editor, Studies in Constructive Mathematics and Mathematical Logic, Part II. 1968.