{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:52:34Z","timestamp":1744217554152},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T00:00:00Z","timestamp":1492560000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00037-017-0152-4","type":"journal-article","created":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T09:27:58Z","timestamp":1492594078000},"page":"911-948","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Tight Size-Degree Bounds for Sums-of-Squares Proofs"],"prefix":"10.1007","volume":"26","author":[{"given":"Massimo","family":"Lauria","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,19]]},"reference":[{"key":"152_CR1","unstructured":"Albert Atserias, Massimo Lauria & Jakob Nordstr\u00f6m (2016). Narrow Proofs May Be Maximally Long. ACM Transactions on Computational Logic 17, 19:1\u201319:30. Preliminary version in CCC \u201914."},{"key":"152_CR2","doi-asserted-by":"crossref","unstructured":"Albert Atserias, Moritz M\u00fcller & Sergi Oliva (2015). Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. Journal of Symbolic Logic 80(2), 450\u2013476. Preliminary version in CCC \u201913.","DOI":"10.1017\/jsl.2014.56"},{"key":"152_CR3","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Fernando G. S. L. Brand\u00e3o, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer & Yuan Zhou (2012). Hypercontractivity, Sum-of-Squares Proofs, and Their Applications. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC \u201912), 307\u2013326.","DOI":"10.1145\/2213977.2214006"},{"key":"152_CR4","unstructured":"Boaz Barak & David Steurer (2014). Sum-of-Squares Proofs and the Quest Toward Optimal Algorithms. Technical Report TR14-059, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"152_CR5","doi-asserted-by":"crossref","unstructured":"Paul Beame, Russell Impagliazzo, Jan Kraj\u00ed\u010dek, Toniann Pitassi & Pavel Pudl\u00e1k (1994). Lower Bounds on Hilbert\u2019s Nullstellensatz and Propositional Proofs. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201994), 794\u2013806.","DOI":"10.1109\/SFCS.1994.365714"},{"key":"152_CR6","doi-asserted-by":"crossref","unstructured":"Paul Beame, Toniann Pitassi & Nathan Segerlind (2007). Lower Bounds for Lov\u00e1sz\u2013Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. SIAM Journal on Computing 37(3), 845\u2013869. Preliminary version in ICALP \u201905.","DOI":"10.1137\/060654645"},{"key":"152_CR7","unstructured":"Olaf Beyersdorff, Nicola Galesi & Massimo Lauria (2013). Parameterized Complexity of DPLL Search Procedures. ACM Transactions on Computational Logic 14(3), 20:1\u201320:21. Preliminary version in SAT \u201911."},{"key":"152_CR8","unstructured":"Olaf Beyersdorff, Nicola Galesi, Massimo Lauria & Alexander A. Razborov (2012). Parameterized Bounded-Depth Frege Is not Optimal. ACM Transactions on Computation Theory 4, 7:1\u20137:16. Preliminary version in ICALP \u201911."},{"key":"152_CR9","doi-asserted-by":"crossref","unstructured":"Stefan S. Dantchev (2006). Relativisation Provides Natural Separations for Resolution-Based Proof Systems. In Proceedings of the 1st International Computer Science Symposium in Russia (CSR \u201906), volume 3967 of Lecture Notes in Computer Science, 147\u2013158. Springer.","DOI":"10.1007\/11753728_17"},{"issue":"3","key":"152_CR10","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1016\/j.apal.2013.10.009","volume":"165","author":"Dantchev. Stefan S.","year":"2014","unstructured":"Stefan S. Dantchev., Barnaby Martin (2014) Relativization Makes Contradictions Harder for Resolution.. Annals of Pure and Applied Logic 165(3): 837\u2013857","journal-title":"Annals of Pure and Applied Logic"},{"key":"152_CR11","unstructured":"Stefan S. Dantchev & S\u00f8ren Riis (2003). On Relativisation and Complexity Gap for Resolution-Based Proof Systems. In Proceedings of the 17th International Workshop on Computer Science Logic (CSL \u201903), volume 2803 of Lecture Notes in Computer Science, 142\u2013154. Springer."},{"issue":"2","key":"152_CR12","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"Feige. Uriel","year":"1996","unstructured":"Uriel Feige., Shafi Goldwasser., Laszlo Lov\u00e1sz., Shmuel Safra., Mario Szegedy (1996) Interactive Proofs and the Hardness of Approximating Cliques. Journal of the ACM 43(2): 268\u2013292","journal-title":"Journal of the ACM"},{"issue":"2","key":"152_CR13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00037-001-8192-0","volume":"10","author":"Grigoriev Dima","year":"2001","unstructured":"Dima Grigoriev (2001a) Complexity of Positivstellensatz proofs for the knapsack.. Computational Complexity 10(2): 139\u2013154","journal-title":"Computational Complexity"},{"issue":"1\u20132","key":"152_CR14","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"Grigoriev Dima","year":"2001","unstructured":"Dima Grigoriev (2001b) Linear Lower Bound on Degrees of Positivstellensatz Calculus Proofs for the Parity. Theoretical Computer Science 259(1\u20132): 613\u2013622","journal-title":"Theoretical Computer Science"},{"key":"152_CR15","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev, Edward A. Hirsch & Dmitrii V. Pasechnik (2002). Exponential Lower Bound for Static Semi-algebraic Proofs. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP \u201902), volume 2380 of Lecture Notes in Computer Science, 257\u2013268. Springer.","DOI":"10.1007\/3-540-45465-9_23"},{"issue":"1\u20133","key":"152_CR16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0168-0072(01)00055-0","volume":"113","author":"Grigoriev. Dima","year":"2001","unstructured":"Dima Grigoriev., Nicolai Vorobjov (2001) Complexity of Null- and Positivstellensatz proofs. Annals of Pure and Applied Logic 113(1\u20133): 153\u2013160","journal-title":"Annals of Pure and Applied Logic"},{"key":"152_CR17","unstructured":"Mika G\u00f6\u00f6s & Toniann Pitassi (2014). Communication Lower Bounds via Critical Block Sensitivity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC \u201914), 847\u2013856."},{"key":"152_CR18","unstructured":"Subhash Khot (2002). On the Power of Unique 2-prover 1-round Games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC \u201902), 767\u2013775."},{"key":"152_CR19","unstructured":"Arist Kojevnikov & Dmitry Itsykson (2006). Lower Bounds of Static Lov\u00e1sz\u2013Schrijver Calculus Proofs for Tseitin Tautologies. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP \u201906), volume 4051 of Lecture Notes in Computer Science, 323\u2013334. Springer."},{"issue":"4","key":"152_CR20","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s00153-003-0186-y","volume":"43","author":"Kraj\u00ed\u010dek Jan","year":"2004","unstructured":"Jan Kraj\u00ed\u010dek (2004) Combinatorics of First Order Structures and Propositional Proof Systems. Archive for Mathematical Logic 43(4): 427\u2013441","journal-title":"Archive for Mathematical Logic"},{"issue":"1","key":"152_CR21","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02807438","volume":"12","author":"Krivine Jean-Louis","year":"1964","unstructured":"Jean-Louis Krivine (1964) Anneaux pr\u00e9ordonn\u00e9s. Journal d\u2019Analyse Math\u00e9matique 12(1): 307\u2013326","journal-title":"Journal d\u2019Analyse Math\u00e9matique"},{"key":"152_CR22","doi-asserted-by":"crossref","unstructured":"Jean B. Lasserre (2001). An explicit exact SDP relaxation for nonlinear 0-1 programs. In Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization (IPCO \u201901), volume 2081 of Lecture Notes in Computer Science, 293\u2013303. Springer.","DOI":"10.1007\/3-540-45535-3_23"},{"key":"152_CR23","unstructured":"Massimo Lauria & Jakob Nordstr\u00f6m (2015). Tight Size-Degree Bounds for Sums-of-Squares Proofs. In Proceedings of the 30th Annual Computational Complexity Conference (CCC \u201915), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), 448\u2013466."},{"key":"152_CR24","doi-asserted-by":"crossref","unstructured":"Massimo Lauria, Pavel Pudl\u00e1k, Vojt\u011bch R\u00f6dl & Neil Thapen (2013). The Complexity of Proving That a Graph is Ramsey. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP \u201913), volume 7965 of Lecture Notes in Computer Science, 684\u2013695. Springer.","DOI":"10.1007\/978-3-642-39206-1_58"},{"key":"152_CR25","doi-asserted-by":"crossref","unstructured":"James R. Lee, Prasad Raghavendra, David Steurer & Ning Tan (2014). On the Power of Symmetric LP and SDP Relaxations. In Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC \u201914), 13\u201321.","DOI":"10.1109\/CCC.2014.10"},{"key":"152_CR26","doi-asserted-by":"crossref","unstructured":"Yurii Nesterov (2000). Squared Functional Systems and Optimization Problems. In High Performance Optimization, H. Frenk, K. Roos, T. Terlaky & S. Zhang, editors, 405\u2013440. Kluwer Academic Publisher.","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"152_CR27","unstructured":"Ryan O\u2019Donnell (2016). SOS is Not Obviously Automatizable, Even Approximately. Technical Report TR16-141, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"152_CR28","doi-asserted-by":"crossref","unstructured":"Ryan O\u2019Donnell & Yuan Zhou (2013). Approximability and Proof Complexity. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201913), 1537\u20131556.","DOI":"10.1137\/1.9781611973105.111"},{"key":"152_CR29","unstructured":"Pablo A. Parrilo (2000). Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. thesis, California Institute of Technology. Available at http:\/\/resolver.caltech.edu\/CaltechETD:etd-05062004-055516 ."},{"key":"152_CR30","doi-asserted-by":"crossref","unstructured":"Toniann Pitassi & Nathan Segerlind (2012). Exponential Lower Bounds and Integrality Gaps for Tree-Like Lov\u00e1sz\u2013Schrijver Procedures. SIAM Journal on Computing 41(1), 128\u2013159. Preliminary version in SODA \u201909.","DOI":"10.1137\/100816833"},{"key":"152_CR31","doi-asserted-by":"crossref","unstructured":"Grant Schoenebeck (2008). Linear Level Lasserre Lower Bounds for Certain k-CSPs. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201908), 593\u2013602.","DOI":"10.1109\/FOCS.2008.74"},{"key":"152_CR32","doi-asserted-by":"crossref","unstructured":"N. Z. Shor (1987). An Approach to Obtaining Global Extremums in Polynomial Mathematical Programming Problems. Cybernetics 23(5), 695\u2013700. Translated from Kibernetika, No. 5, pages 102\u2013106, 1987.","DOI":"10.1007\/BF01074929"},{"issue":"2","key":"152_CR33","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01362149","volume":"207","author":"Stengle Gilbert","year":"1973","unstructured":"Gilbert Stengle (1973) A Nullstellensatz and a Positivstellensatz in Semialgebraic Geometry. Mathematische Annalen 207(2): 87\u201397","journal-title":"Mathematische Annalen"},{"key":"152_CR34","doi-asserted-by":"crossref","unstructured":"Madhur Tulsiani (2009). CSP Gaps and Reductions in the Lasserre Hierarchy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC \u201909), 303\u2013312.","DOI":"10.1145\/1536414.1536457"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0152-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0152-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0152-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T04:47:55Z","timestamp":1569041275000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0152-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,19]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["152"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0152-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,19]]}}}