{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T11:07:55Z","timestamp":1768648075956,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":68,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["PZ00P2\\_174117"],"award-info":[{"award-number":["PZ00P2\\_174117"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WO 2206\/1-1"],"award-info":[{"award-number":["WO 2206\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,8]]},"DOI":"10.1145\/3326229.3326269","type":"proceedings-article","created":{"date-parts":[[2019,7,9]],"date-time":"2019-07-09T12:53:20Z","timestamp":1562676800000},"page":"251-258","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["New Dependencies of Hierarchies in Polynomial Optimization"],"prefix":"10.1145","author":[{"given":"Adam","family":"Kurpisz","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich , Switzerland"}]},{"given":"Timo","family":"de Wolff","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Braunschweig, Braunschweig, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2014.6814141"},{"key":"e_1_3_2_1_2_1","volume-title":"CDC 2014","author":"Ahmadi A. A.","year":"2014","unstructured":"A. A. Ahmadi, A. Majumdar, and R. Tedrake. 2014. Control and verification of high-dimensional systems with DSOS and SDSOS programming. In CDC 2014, Los Angeles, CA, USA, December 15--17, 2014. 394--401."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867834"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_6_1","volume-title":"COLT 2016","author":"Barak B.","year":"2016","unstructured":"B. Barak and A. Moitra. 2016. Noisy Tensor Completion via the Sum-of-Squares Hierarchy. In COLT 2016, New York, USA, June 23--26, 2016. 417--445."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","unstructured":"B. Barak P. Raghavendra and D. Steurer. 2011. Rounding Semidefinite Programming Hierarchies via Global Correlation. In FOCS . 472--481. 10.1109\/FOCS.2011.95","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_8_1","first-page":"59","article-title":"Sum-of-squares proofs and the quest toward optimal algorithms","volume":"21","author":"Barak B.","year":"2014","unstructured":"B. Barak and D. Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. Electronic Colloquium on Computational Complexity (ECCC), Vol. 21 (2014), 59.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1975.57.15"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"M. H. Bateni M. Charikar and V. Guruswami. 2009. MaxMin allocation via degree lower-bounded arborescences. In STOC . 543--552. 10.1145\/1536414.1536488","DOI":"10.1145\/1536414.1536488"},{"key":"e_1_3_2_1_11_1","volume-title":"Stabbing Planes. In ITCS 2018","author":"Beame P.","year":"2018","unstructured":"P. Beame, N. Fleming, R. Impagliazzo, A. Kolokolova, D. Pankratov, T. Pitassi, and R. Robere. 2018. Stabbing Planes. In ITCS 2018, January 11--14, 2018, Cambridge, MA, USA. 10:1--10:20."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"S. Boyd and L. Vandenberghe. 2004. Convex Optimization .Cambridge University Press New York NY USA.","DOI":"10.5555\/993483"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_3_2_1_14_1","unstructured":"V. Chandrasekaran R. Murray and A. Wierman. 2018. Newton Polytopes and Relative Entropy Optimization. Preprint; see arXiv:1810.01614."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/140988978"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0998-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"E. Chlamtac. 2007. Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. In FOCS . 691--701. 10.1109\/FOCS.2007.13","DOI":"10.1109\/FOCS.2007.13"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"E. Chlamtac and G. Singh. 2008. Improved Approximation Guarantees through Higher Levels of SDP Hierarchies. In APPROX-RANDOM . 49--62. 10.1007\/978-3-540-85363-3_5","DOI":"10.1007\/978-3-540-85363-3_5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"E. Chlamtac and M. Tulsiani. 2012. Convex relaxations and integrality gaps. In to appear in Handbook on semidefinite conic and polynomial optimization. Springer.","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627842"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"W. F. de la Vega and C. Kenyon-Mathieu. 2007. Linear programming relaxations of maxcut. In SODA. 53--61.","DOI":"10.5555\/1283383.1283390"},{"key":"e_1_3_2_1_22_1","first-page":"53","article-title":"Amoebas, Nonnegative Polynomials and Sums of Squares Supported on Circuits","volume":"23","author":"de Wolff T.","year":"2015","unstructured":"T. de Wolff. 2015. Amoebas, Nonnegative Polynomials and Sums of Squares Supported on Circuits. Oberwolfach Rep. 23 (2015), 53--56.","journal-title":"Oberwolfach Rep."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"G. Dias and L. Liberti. 2016. Diagonally Dominant Programming in Distance Geometry. In Combinatorial Optimization . Springer International Publishing Cham 225--236.","DOI":"10.1007\/978-3-319-45587-7_20"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1086303"},{"key":"e_1_3_2_1_25_1","volume-title":"MFCS 2018","author":"Dressler M.","year":"2018","unstructured":"M. Dressler, A. Kurpisz, and T. de Wolff. 2018a. Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials. In MFCS 2018, August 27--31, 2018, Liverpool, UK. 82:1--82:17."},{"key":"e_1_3_2_1_26_1","unstructured":"M. Dressler H. Naumann and T. Theobald. 2018b. The dual cone of sums of non-negative circuit polynomials. Preprint; see arXiv:1809.07648."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.759239"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"V. Guruswami and A. K. Sinop. 2011. Lasserre Hierarchy Higher Eigenvalues and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. In FOCS . 482--491. 10.1109\/FOCS.2011.36","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40687-016-0052-2"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02807438"},{"key":"e_1_3_2_1_35_1","first-page":"3417","article-title":"b. Quelques propri\u00e9t\u00e9s des pr\u00e9ordres dans les anneaux commutatifs unitaires","volume":"258","author":"Krivine J.-L.","year":"1964","unstructured":"J.-L. Krivine. 1964 b. Quelques propri\u00e9t\u00e9s des pr\u00e9ordres dans les anneaux commutatifs unitaires. C. R. Acad. Sci. Paris, Vol. 258 (1964), 3417--3418.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"e_1_3_2_1_36_1","article-title":"Alternative SDP and SOCP approximations for polynomial optimization. EURO","author":"Kuang X.","year":"2018","unstructured":"X. Kuang, B. Ghaddar, J. Naoum-Sawaya, and L. F. Zuluaga. 2018. Alternative SDP and SOCP approximations for polynomial optimization. EURO J. Comput. Optim. (13 Aug 2018).","journal-title":"J. Comput. Optim. (13"},{"key":"e_1_3_2_1_37_1","volume-title":"New Dependencies of Hierarchies in Polynomial Optimization. CoRR","author":"Kurpisz A.","year":"2019","unstructured":"A. Kurpisz and T. de Wolff. 2019. New Dependencies of Hierarchies in Polynomial Optimization. CoRR, Vol. abs\/1903.04996 (2019). arxiv: 1903.04996"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_1_40_1","volume-title":"Emerging applications of algebraic geometry. IMA","author":"Laurent M.","unstructured":"M. Laurent. 2009. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry. IMA Vol. Math. Appl., Vol. 149. Springer, New York, 157--270."},{"key":"e_1_3_2_1_41_1","unstructured":"J. Lee. 2015. Semi-definite extended formulations and sums of squares. In Lecture notes for the Summer School on Combinatorial Optimization Summer School on Combinatorial Optimization Bonn ."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","unstructured":"J. R. Lee P. Raghavendra and D. Steurer. 2015. Lower Bounds on the Size of Semidefinite Programming Relaxations. In STOC . 567--576. 10.1145\/2746539.2746599","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_3_2_1_43_1","unstructured":"Y.P. Leong. 2018. Optimal Controller Synthesis for Nonlinear Systems."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"E. Levey and T. Rothvoss. 2016. A (1","DOI":"10.1145\/3127497"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897532"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","unstructured":"A. Magen and M. Moharrami. 2009. Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. In APPROX-RANDOM. 258--271. 10.1007\/978-3-642-03685-9_20","DOI":"10.1007\/978-3-642-03685-9_20"},{"key":"e_1_3_2_1_47_1","volume-title":"Positive polynomials and sums of squares . Mathematical Surveys and Monographs","author":"Marshall M.","unstructured":"M. Marshall. 2008. Positive polynomials and sums of squares . Mathematical Surveys and Monographs, Vol. 146. American Mathematical Society, Providence, RI."},{"key":"e_1_3_2_1_48_1","volume-title":"Bienstock-Zuckerberg Hierarchy and CG Cuts. In IPCO 2017, Waterloo, ON, Canada, June 26--28, 2017, Proceedings. 405--416","author":"Mastrolilli M.","year":"2017","unstructured":"M. Mastrolilli. 2017. High Degree Sum of Squares Proofs, Bienstock-Zuckerberg Hierarchy and CG Cuts. In IPCO 2017, Waterloo, ON, Canada, June 26--28, 2017, Proceedings. 405--416."},{"key":"e_1_3_2_1_49_1","volume-title":"Global quadratic optimization via conic relaxation","author":"Nesterov Y.","unstructured":"Y. Nesterov. 2000. Global quadratic optimization via conic relaxation .Kluwer Academic Publishers, 363--384."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii. 1994. Interior Point Polynomial Algorithms in Convex Programming .Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611970791"},{"key":"e_1_3_2_1_51_1","first-page":"141","article-title":"SOS is not obviously automatizable, even approximately","volume":"23","author":"O'Donnell R.","year":"2016","unstructured":"R. O'Donnell. 2016. SOS is not obviously automatizable, even approximately. Electronic Colloquium on Computational Complexity (ECCC), Vol. 23 (2016), 141.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_53_1","volume-title":"2015 European Control Conference (ECC). 3091--3096","author":"Peni T.","unstructured":"T. Peni and H. Pfifer. 2015. Analysis of large scale parameter-varying systems by using scaled diagonal dominance. In 2015 European Control Conference (ECC). 3091--3096."},{"key":"e_1_3_2_1_54_1","volume-title":"COLT 2017","author":"Potechin A.","year":"2017","unstructured":"A. Potechin and D. Steurer. 2017. Exact tensor completion with sum-of-squares. In COLT 2017, Amsterdam, The Netherlands, 7--10 July 2017. 1619--1673."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","unstructured":"P. Raghavendra and N. Tan. 2012. Approximating CSPs with global cardinality constraints using SDP hierarchies. In SODA . 373--387.","DOI":"10.5555\/2095116.2095149"},{"key":"e_1_3_2_1_57_1","volume-title":"On the Bit Complexity of Sum-of-Squares Proofs. In ICALP 2017","author":"Raghavendra P.","year":"2017","unstructured":"P. Raghavendra and B. Weitz. 2017. On the Bit Complexity of Sum-of-Squares Proofs. In ICALP 2017, July 10--14, 2017, Warsaw, Poland . 80:1--80:13."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442738"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"E. Salgado A. Scozzari F. Tardella and L. Liberti. 2018. Alternating Current Optimal Power Flow with Generator Selection. In Combinatorial Optimization. Springer International Publishing Cham 364--375.","DOI":"10.1007\/978-3-319-96151-4_31"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446568"},{"key":"e_1_3_2_1_61_1","volume-title":"COLT 2017","author":"Schramm T.","year":"2017","unstructured":"T. Schramm and D. Steurer. 2017. Fast and robust tensor decomposition with applications to dictionary learning. In COLT 2017, Amsterdam, The Netherlands, 7--10 July 2017 . 1760--1793."},{"key":"e_1_3_2_1_62_1","unstructured":"H. Seidler and T. de Wolff. 2018. An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization. Preprint see ArXiv:1808.08431."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2016.7526778"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079245"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-013-9662-4"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Y. Zheng G. Fantuzzi and A. Papachristodoulou. 2018. Sparse sum-of-squares (SOS) optimization: A bridge between DSOS\/SDSOS and SOS optimization for sparse polynomials. CoRR Vol. abs\/1807.05463 (2018). arxiv: 1807.05463","DOI":"10.23919\/ACC.2019.8814998"},{"key":"e_1_3_2_1_69_1","volume-title":"Lectures on Polytopes","author":"Ziegler G.M.","unstructured":"G.M. Ziegler. 2007. Lectures on Polytopes .Springer Verlag."}],"event":{"name":"ISSAC '19: International Symposium on Symbolic and Algebraic Computation","location":"Beijing China","acronym":"ISSAC '19","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"]},"container-title":["Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326229.3326269","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326229.3326269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:00Z","timestamp":1750206360000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326229.3326269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,8]]},"references-count":68,"alternative-id":["10.1145\/3326229.3326269","10.1145\/3326229"],"URL":"https:\/\/doi.org\/10.1145\/3326229.3326269","relation":{},"subject":[],"published":{"date-parts":[[2019,7,8]]},"assertion":[{"value":"2019-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}