{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:11Z","timestamp":1771623791611,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540432838","type":"print"},{"value":"9783540458418","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_34","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:11:17Z","timestamp":1186906277000},"page":"419-430","source":"Crossref","is-referenced-by-count":24,"title":["Complexity of Semi-algebraic Proofs"],"prefix":"10.1007","author":[{"given":"Dima","family":"Grigoriev","sequence":"first","affiliation":[]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[]},{"given":"Dmitrii V.","family":"Pasechnik","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semi-algebraic proofs. Technical report, Electronic Colloquim on Computational Complexity (2001(submitted)) http:\/\/eccc.uni-trier.de\/eccc-local\/Lists\/TR-2001.html .","DOI":"10.1007\/3-540-45841-7_34"},{"key":"34_CR2","doi-asserted-by":"crossref","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. London Math. Soc. 73 (1996) 1\u201326","journal-title":"Proc. London Math. Soc."},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/BF01294258","volume":"6","author":"P. Beame","year":"1996\/97","unstructured":"Beame, P., Impagliazzo, R., Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Razborov, A.A., Sgall, J.: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity 6 (1996\/97) 256\u2013298","journal-title":"Computational Complexity"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s000370050013","volume":"7","author":"A.A. Razborov","year":"1998","unstructured":"Razborov, A.A.: Lower bounds for the polynomial calculus. Computational Complexity 7 (1998) 291\u2013324","journal-title":"Computational Complexity"},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s000370050024","volume":"8","author":"R. Impagliazzo","year":"1999","unstructured":"Impagliazzo, R., Pudl\u00e1k, P., Sgall, J.: Lower bounds for the polynomial calculus. Computational Complexity 8 (1999) 127\u2013144","journal-title":"Computational Complexity"},{"key":"34_CR6","unstructured":"Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatis.ability. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC\u201996, ACM (1996) 174\u2013183"},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jcss.2000.1726","volume":"62","author":"S. Buss","year":"2001","unstructured":"Buss, S., Grigoriev, D., Impagliazzo, R., Pitassi, T.: Linear gaps between degrees for the polynomial calculus modulo distinct primes. Journal of Computer and System Sciences 62 (2001) 267\u2013289","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR8","unstructured":"Grigoriev, D., Hirsch, E.A.: Algebraic proof systems over formulas. Technical Report 01-011, Electronic Colloquim on Computational Complexity (2001) ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/2001\/TR01-011\/index.html ."},{"key":"34_CR9","unstructured":"Gomory, R.E.: An algorithm for integer solutions of linear programs. In: Recent Advances in Mathematical Programming. McGraw-Hill (1963) 269\u2013302"},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4 (1973) 305\u2013337","journal-title":"Discrete Math"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook, W., Coullard, C.R., Tur\u00e1n, G.: On the complexity of cutting-plane proofs. Discrete Appl. Math. 18(1987) 25\u201338","journal-title":"Discrete Appl. Math."},{"issue":"115","key":"34_CR12","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114","author":"V. Chv\u00e1tal","year":"1989","unstructured":"Chv\u00e1tal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114\/115(1989) 455\u2013499","journal-title":"Linear Algebra Appl."},{"key":"34_CR13","unstructured":"Bonet, M., Pitassi, T., Raz, R.: Lower bounds for Cutting Planes proofs with small coeficients. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, STOC\u201995, ACM (1995) 575\u2013584"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symbolic Logic 62(1997) 981\u2013998","journal-title":"J. Symbolic Logic"},{"key":"34_CR15","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 Journal on Optimization 1 (1991) 166\u2013190","journal-title":"SIAM Journal on Optimization"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0012-365X(92)00057-X","volume":"124","author":"L. Lov\u00e1sz","year":"1994","unstructured":"Lov\u00e1sz, L.: Stable sets and polynomials. Discrete Mathematics 124 (1994) 137\u2013153","journal-title":"Discrete Mathematics"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Pudl\u00e1k, P.: On the complexity of propositional calculus. In: Sets and Proofs: Invited papers from Logic Colloquium\u201997. Cambridge University Press (1999) 197\u2013218","DOI":"10.1017\/CBO9781107325944.010"},{"key":"34_CR18","first-page":"1033","volume":"22","author":"A. Razborov","year":"1985","unstructured":"Razborov, A.: Lower bounds on the monotone complexity of boolean functions. Dokl. AN USSR 22(1985) 1033\u20131037","journal-title":"Dokl. AN USSR"},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0168-0072(01)00055-0","volume":"113","author":"D. Grigoriev","year":"2001","unstructured":"Grigoriev, D., Vorobjov, N.: Complexity of Null-and Positivstellensatz proofs. Annals of Pure and Applied Logic 113(2001) 153\u2013160","journal-title":"Annals of Pure and Applied Logic"},{"key":"34_CR20","doi-asserted-by":"crossref","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. Theoretical Computer Science 259 (2001) 613\u2013622","journal-title":"Theoretical Computer Science"},{"key":"34_CR21","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. Computational Complexity 10(2001) 139\u2013154","journal-title":"Computational Complexity"},{"key":"34_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T. Stephen","year":"1999","unstructured":"Stephen, T., Tun\u00e7el, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24 (1999) 1\u20137","journal-title":"Math. Oper. Res."},{"key":"34_CR23","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/moor.26.1.19.10593","volume":"26","author":"W. Cook","year":"2001","unstructured":"Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26 (2001) 19\u201330","journal-title":"Math. Oper. Res."},{"key":"34_CR24","unstructured":"Dash, S.: On the Matrix Cuts of Lov\u00e1sz and Schrijver and their use in Integer Programming. Technical report tr01-08, Rice University (2001) http:\/\/www.caam.rice.edu\/caam\/trs\/2001\/TR01-08.ps ."},{"key":"34_CR25","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Tun\u00e7el, L.: When does the positive semidefiniteness constraint help in lifting procedures. Mathematics of Operations Research (2001) to appear.","DOI":"10.1287\/moor.26.4.796.10012"},{"key":"34_CR26","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00156-0","volume":"98","author":"A. Bockmayr","year":"1999","unstructured":"Bockmayr, A., Eisenbrand, F., Hartmann, M., Schulz, A.S.: On the Chv\u00e1tal rank of polytopes in the 0\/1 cube. Discrete Applied Mathematics 98 (1999) 21\u201327","journal-title":"Discrete Applied Mathematics"},{"key":"34_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/3-540-48777-8_11","volume-title":"IPCO\u201999","author":"F. Eisenbrand","year":"1999","unstructured":"Eisenbrand, F., Schulz, A.S.: Bounds on the Chv\u00e1tal rank of polytopes in the 0\/1-cube. In G. Cornu\u00e9jos, R.E. Burkard, G., ed.: IPCO\u201999. Volume 1610 of Lecture Notes in Computer Science., Berlin Heidelberg, Springer-Verlag (1999) 137\u2013150"},{"key":"34_CR28","doi-asserted-by":"crossref","unstructured":"Urquhart, A.: Hard examples for resolution. JACM 34 (1987)","DOI":"10.1145\/7531.8928"},{"key":"34_CR29","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E.: Hard examples for bounded depth Frege. Manuscript (2001)","DOI":"10.1145\/509907.509988"},{"key":"34_CR30","doi-asserted-by":"publisher","first-page":"1582","DOI":"10.2307\/2586668","volume":"63","author":"J. Kraj\u00ed\u010dek","year":"1998","unstructured":"Kraj\u00ed\u010dek, J.: Discretely ordered modules as a first-order extension of the cutting planes proof system. Journal of Symbolic Logic 63 (1998) 1582\u20131596","journal-title":"Journal of Symbolic Logic"},{"key":"34_CR31","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, A.R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44 (1979) 36\u201350","journal-title":"Journal of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:56:16Z","timestamp":1737363376000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_34","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}