{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T05:05:30Z","timestamp":1736831130866,"version":"3.33.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2006,9,1]],"date-time":"2006-09-01T00:00:00Z","timestamp":1157068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2006,9,1]],"date-time":"2006-09-01T00:00:00Z","timestamp":1157068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2006,9]]},"DOI":"10.1007\/s10472-006-9041-2","type":"journal-article","created":{"date-parts":[[2007,1,29]],"date-time":"2007-01-29T10:59:58Z","timestamp":1170068398000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs"],"prefix":"10.1007","volume":"48","author":[{"given":"Miguel F.","family":"Anjos","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,1,30]]},"reference":[{"key":"9041_CR1","unstructured":"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)"},{"key":"9041_CR2","doi-asserted-by":"crossref","unstructured":"Anjos, M.F.: On semidefinite programming relaxations for the satisfiability problem. Math. Methods Oper. Res. 60(3) (2004)","DOI":"10.1007\/s001860400377"},{"key":"9041_CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/978-3-642-17022-5_40","volume-title":"Operations Research Proceedings 2003","author":"M.F. Anjos","year":"2004","unstructured":"Anjos, M.F.: Proofs of unsatisfiability via semidefinite programming. In: Operations Research Proceedings 2003, pp. 308\u2013315. Springer, Berlin Heidelberg New York (2004)"},{"issue":"3","key":"9041_CR4","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s10107-003-0495-2","volume":"102","author":"M.F. Anjos","year":"2005","unstructured":"Anjos, M.F.: An improved semidefinite programming relaxation for the satisfiability problem. Math. Program. 102(3), 589\u2013608 (2005)","journal-title":"Math. Program."},{"issue":"3","key":"9041_CR5","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/A:1014895808844","volume":"6","author":"M.F. Anjos","year":"2002","unstructured":"Anjos, M.F., Wolkowicz, H.: Geometry of semidefinite max-cut relaxations via matrix ranks. J. Comb. Optim. 6(3), 237\u2013270 (2002)","journal-title":"J. Comb. Optim."},{"issue":"1\u20132","key":"9041_CR6","first-page":"513","volume":"123","author":"M.F. Anjos","year":"2002","unstructured":"Anjos, M.F., Wolkowicz, H.: Semidefinite programming for discrete optimization and matrix completion problems. Discrete Appl. Math. 123(1\u20132), 513\u2013577 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"9041_CR7","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0166-218X(01)00266-9","volume":"119","author":"M.F. Anjos","year":"2002","unstructured":"Anjos, M.F., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discrete Appl. Math. 119(1\u20132), 79\u2013106 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"3, Ser. A","key":"9041_CR8","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58(3, Ser. A), 295\u2013324 (1993)","journal-title":"Math. Program."},{"issue":"1","key":"9041_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/plms\/s3-73.1.1","volume":"73","author":"P. Beame","year":"1996","unstructured":"Beame, P., Impagliazzo, R., Kraj\u00ed\u010dek, J., Pitassi, T., Pudl\u00e1k, P.: Lower bounds on Hilbert\u2019s Nullstellensatz and propositional proofs. Proc. Lond. Math. Soc.\u00a0(3) 73(1), 1\u201326 (1996)","journal-title":"Proc. Lond. Math. Soc.\u00a0(3)"},{"issue":"5","key":"9041_CR10","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/0305-0548(86)90056-0","volume":"13","author":"C.E. Blair","year":"1986","unstructured":"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\u2013645 (1986)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"9041_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(94)90033-7","volume":"55","author":"E. Boros","year":"1994","unstructured":"Boros, E., Hammer, P.L., Sun, X.: Recognition of q-Horn formulae in linear time. Discrete Appl. Math. 55(1), 1\u201313 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9041_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013327 (October 2003)","DOI":"10.1109\/SFCS.2003.1238206"},{"key":"9041_CR13","volume-title":"Optimization Methods for Logical Inference. Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"V. Chandru","year":"1999","unstructured":"Chandru, V., Hooker, J.: Optimization Methods for Logical Inference. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)"},{"issue":"3","key":"9041_CR14","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1023\/A:1021208315170","volume":"37","author":"E. de Klerk","year":"2003","unstructured":"de\u00a0Klerk, E., van Maaren, H.: On semidefinite programming relaxations of (2+p)-SAT. Ann. Math. Artif. Intell. 37(3), 285\u2013305 (2003)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"1, 2","key":"9041_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/A:1006362203438","volume":"24","author":"E. de Klerk","year":"2000","unstructured":"de\u00a0Klerk, E., van Maaren, H., Warners, J.P.: Relaxations of the satisfiability problem using semidefinite programming. J. Autom. Reason. 24(1, 2), 37\u201365 (2000)","journal-title":"J. Autom. Reason."},{"issue":"6","key":"9041_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"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\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9041_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R.E. Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Amer. Math. Soc."},{"key":"9041_CR18","first-page":"269","volume-title":"Recent Advances in Mathematical Programming","author":"R.E. Gomory","year":"1963","unstructured":"Gomory, R.E.: An algorithm for integer solutions to linear programs. In: Recent Advances in Mathematical Programming, pp. 269\u2013302. McGraw-Hill, New York (1963)"},{"issue":"2","key":"9041_CR19","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00037-001-8192-0","volume":"10","author":"D. Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Comput. Complex. 10(2), 139\u2013154 (2001)","journal-title":"Comput. Complex."},{"issue":"1, 2","key":"9041_CR20","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"D. Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comp. Sci. 259(1, 2), 613\u2013622 (2001)","journal-title":"Theor. Comp. Sci."},{"issue":"4","key":"9041_CR21","doi-asserted-by":"crossref","first-page":"647","DOI":"10.17323\/1609-4514-2002-2-4-647-679","volume":"2","author":"D. Grigoriev","year":"2002","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semialgebraic proofs. Mosc. Math. J. 2(4), 647\u2013679 (2002)","journal-title":"Mosc. Math. J."},{"issue":"1\u20133","key":"9041_CR22","first-page":"153","volume":"113","author":"D. Grigoriev","year":"2002","unstructured":"Grigoriev, D., Vorobjov, N.: Complexity of null- and Positivstellensatz proofs. Ann. Pure Appl. Logic 113(1\u20133), 153\u2013160 (2002)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9041_CR23","unstructured":"Helmberg, C.: http:\/\/www-user.tu-chemnitz.de\/~helmberg\/semidef.html"},{"key":"9041_CR24","unstructured":"Lasserre, J.B.: Optimality conditions and LMI relaxations for 0-1 programs. Technical report, LAAS-CNRS, Toulouse, France (2000)"},{"issue":"3","key":"9041_CR25","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"J.B. Lasserre","year":"2000\/01","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (electronic) (2000\/01)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"9041_CR26","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"J.B. Lasserre","year":"2002","unstructured":"Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J. Optim. 12(3), 756\u2013769 (electronic) (2002)","journal-title":"SIAM J. Optim."},{"key":"9041_CR27","doi-asserted-by":"crossref","unstructured":"Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Handbook on Discrete Optimization, pp. 393\u2013514. Elsevier B.V. (2005)","DOI":"10.1016\/S0927-0507(05)12008-8"},{"issue":"2","key":"9041_CR28","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"issue":"2, Ser. B","key":"9041_CR29","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"P.A. Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2, Ser. B), 293\u2013320 (2003)","journal-title":"Math. Program."},{"issue":"3","key":"9041_CR30","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"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\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"9041_CR31","doi-asserted-by":"crossref","unstructured":"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\u2013125. Steklov Mathematical Institute (1968)","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"9041_CR32","first-page":"294","volume-title":"SAT 2005. Lecture Notes in Comput. Sci., vol. 3569","author":"H. van Maaren","year":"2005","unstructured":"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\u2013308. Springer, Berlin Heidelberg New York (2005)"},{"issue":"1","key":"9041_CR33","first-page":"18","volume":"13","author":"H.P. Williams","year":"1977","unstructured":"Williams, H.P.: Logical problems and integer programming. Bull. Inst. Math. Appl. 13(1), 18\u201320 (1977)","journal-title":"Bull. Inst. Math. Appl."},{"volume-title":"Handbook of Semidefinite Programming","year":"2000","key":"9041_CR34","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. Kluwer, Boston, MA (2000)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-006-9041-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-006-9041-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-006-9041-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-006-9041-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T06:56:00Z","timestamp":1736751360000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-006-9041-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":34,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["9041"],"URL":"https:\/\/doi.org\/10.1007\/s10472-006-9041-2","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"30 January 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}