An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs

Anjos, M.F.: New convex relaxations for the maximum cut and VLSI layout problems. Ph.D. thesis, University of Waterloo. Published online at http://etd.uwaterloo.ca/etd/manjos2001.pdf (2001)

Anjos, M.F.: On semidefinite programming relaxations for the satisfiability problem. Math. Methods Oper. Res. 60(3) (2004)

Anjos, M.F.: Proofs of unsatisfiability via semidefinite programming. In: Operations Research Proceedings 2003, pp. 308–315. Springer, Berlin Heidelberg New York (2004)

Anjos, M.F.: An improved semidefinite programming relaxation for the satisfiability problem. Math. Program. 102(3), 589–608 (2005)

Anjos, M.F., Wolkowicz, H.: Geometry of semidefinite max-cut relaxations via matrix ranks. J. Comb. Optim. 6(3), 237–270 (2002)

Anjos, M.F., Wolkowicz, H.: Semidefinite programming for discrete optimization and matrix completion problems. Discrete Appl. Math. 123(1–2), 513–577 (2002)

Anjos, M.F., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discrete Appl. Math. 119(1–2), 79–106 (2002)

Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58(3, Ser. A), 295–324 (1993)

Beame, P., Impagliazzo, R., Krajíček, J., Pitassi, T., Pudlák, P.: Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Proc. Lond. Math. Soc. (3) 73(1), 1–26 (1996)

Blair, C.E., Jeroslow, R.G., Lowe, J.K.: Some results and experiments in programming techniques for propositional logic. Comput. Oper. Res. 13(5), 633–645 (1986)

Boros, E., Hammer, P.L., Sun, X.: Recognition of q-Horn formulae in linear time. Discrete Appl. Math. 55(1), 1–13 (1994)

Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting plane procedures. In: Proc. FOCS 2003, pp. 318–327 (October 2003)

Chandru, V., Hooker, J.: Optimization Methods for Logical Inference. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)

de Klerk, E., van Maaren, H.: On semidefinite programming relaxations of (2+p)-SAT. Ann. Math. Artif. Intell. 37(3), 285–305 (2003)

de Klerk, E., van Maaren, H., Warners, J.P.: Relaxations of the satisfiability problem using semidefinite programming. J. Autom. Reason. 24(1, 2), 37–65 (2000)

Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42(6), 1115–1145 (1995)

Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64, 275–278 (1958)

Gomory, R.E.: An algorithm for integer solutions to linear programs. In: Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963)

Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Comput. Complex. 10(2), 139–154 (2001)

Grigoriev, D.: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comp. Sci. 259(1, 2), 613–622 (2001)

Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semialgebraic proofs. Mosc. Math. J. 2(4), 647–679 (2002)

Grigoriev, D., Vorobjov, N.: Complexity of null- and Positivstellensatz proofs. Ann. Pure Appl. Logic 113(1–3), 153–160 (2002)

Helmberg, C.: http://www-user.tu-chemnitz.de/~helmberg/semidef.html

Lasserre, J.B.: Optimality conditions and LMI relaxations for 0-1 programs. Technical report, LAAS-CNRS, Toulouse, France (2000)

Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (electronic) (2000/01)

Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J. Optim. 12(3), 756–769 (electronic) (2002)

Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Handbook on Discrete Optimization, pp. 393–514. Elsevier B.V. (2005)

Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166–190 (1991)

Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2, Ser. B), 293–320 (2003)

Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411–430 (1990)

Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Structures in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics (translated from Russian), pp. 115–125. Steklov Mathematical Institute (1968)

van Maaren, H., van Norden, L.: Sums of squares, satisfiability and maximum satisfiability. In: SAT 2005. Lecture Notes in Comput. Sci., vol. 3569, pp. 294–308. Springer, Berlin Heidelberg New York (2005)

Williams, H.P.: Logical problems and integer programming. Bull. Inst. Math. Appl. 13(1), 18–20 (1977)

Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. Kluwer, Boston, MA (2000)