{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:10:26Z","timestamp":1725484226137},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_23","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"257-268","source":"Crossref","is-referenced-by-count":4,"title":["Exponential Lower Bound for Static 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,6,25]]},"reference":[{"key":"23_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/3-540-45841-7_34","volume-title":"Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science, STACS 2002","author":"D. Grigoriev","year":"2002","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semi-algebraic proofs. In: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science, STACS 2002. Volume 2285 of Lecture Notes in Computer Science., Springer (2002) 419\u2013430"},{"key":"23_CR2","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":"23_CR3","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":"23_CR4","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. London Math. Soc. 73 (1996) 1\u201326","journal-title":"Proc. London Math. Soc."},{"issue":"\/97","key":"23_CR5","first-page":"256","volume":"6","author":"P. Beame","year":"1996","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":"23_CR6","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":"23_CR7","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":"23_CR8","doi-asserted-by":"crossref","unstructured":"Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC\u201996, ACM (1996) 174\u2013183","DOI":"10.1145\/237814.237860"},{"key":"23_CR9","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":"23_CR10","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":"23_CR11","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"},{"key":"23_CR12","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 semidef-inite liftings. Math. Oper. Res. 24 (1999) 1\u20137","journal-title":"Math. Oper. Res."},{"key":"23_CR13","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":"23_CR14","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":"23_CR15","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":"23_CR16","unstructured":"Gomory, R.E.: An algorithm for integer solutions of linear programs. In: Recent Advances in Mathematical Programming. McGraw-Hill (1963) 269\u2013302"},{"key":"23_CR17","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":"23_CR18","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"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114\/115","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":"23_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1002\/mana.3211810110","volume":"181","author":"H. Lombardi","year":"1996","unstructured":"Lombardi, H., Mnev, N., Roy, M.F.: The Positivstellensatz and small deduction rules for systems of inequalities. Mathematische Nachrichten 181 (1996) 245\u2013259","journal-title":"Mathematische Nachrichten"},{"key":"23_CR21","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":"23_CR22","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. Theoretical Computer Science 259 (2001) 613\u2013622","journal-title":"Theoretical Computer Science"},{"key":"23_CR23","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":"23_CR24","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"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Pitassi, T.: Algebraic propositional proof systems. In Immerman, N., Kolaitis, P.G., eds.: Descriptive Complexity and Finite Models. Volume 31 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society (1997)","DOI":"10.1090\/dimacs\/031\/07"},{"key":"23_CR26","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semi-algebraic proofs. Technical Report 01-103, Revision 01, Electronic Colloquim on Computational Complexity (2002) ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/2001\/TR01-103\/index. html#R01"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T11:05:58Z","timestamp":1556449558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}