{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T12:23:01Z","timestamp":1768652581651,"version":"3.49.0"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T00:00:00Z","timestamp":1617667200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T00:00:00Z","timestamp":1617667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004871","name":"Technische Universit\u00e4t Braunschweig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems is based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization problems over the boolean hypercube via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS-based certificates remain valid: First, for polynomials, which are nonnegative over the <jats:italic>n<\/jats:italic>-variate boolean hypercube with constraints of degree <jats:italic>d<\/jats:italic> there exists a SONC certificate of degree at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$n+d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Second, if there exists a degree <jats:italic>d<\/jats:italic> SONC certificate for nonnegativity of a polynomial over the boolean hypercube, then there also exists a short degree <jats:italic>d<\/jats:italic> SONC certificate that includes at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$n^{O(d)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> nonnegative circuit polynomials. Moreover, we prove that, in opposite to SOS, the SONC cone is not closed under taking affine transformation of variables and that for SONC there does not exist an equivalent to Putinar\u2019s Positivstellensatz for SOS. We discuss these results from both the algebraic and the optimization perspective.\n<\/jats:p>","DOI":"10.1007\/s10208-021-09496-x","type":"journal-article","created":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T21:02:58Z","timestamp":1617742978000},"page":"365-387","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials"],"prefix":"10.1007","volume":"22","author":[{"given":"Mareike","family":"Dressler","sequence":"first","affiliation":[]},{"given":"Adam","family":"Kurpisz","sequence":"additional","affiliation":[]},{"given":"Timo","family":"de Wolff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,6]]},"reference":[{"key":"9496_CR1","doi-asserted-by":"crossref","unstructured":"S.\u00a0Arora, B.\u00a0Barak, and D.\u00a0Steurer, Subexponential algorithms for unique games and related problems, FOCS, 2010, pp.\u00a0563\u2013572.","DOI":"10.1109\/FOCS.2010.59"},{"issue":"2","key":"9496_CR2","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"S.\u00a0Arora, S.\u00a0Rao, and U.\u00a0V. Vazirani, Expander flows, geometric embeddings and graph partitioning, J. ACM 56 (2009), no.\u00a02, 5:1\u20135:37.","journal-title":"J. ACM"},{"key":"9496_CR3","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, S.\u00a0B. Hopkins, J.\u00a0A. Kelner, P.\u00a0Kothari, A.\u00a0Moitra, and A.\u00a0Potechin, A nearly tight sum-of-squares lower bound for the planted clique problem, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, 2016, pp.\u00a0428\u2013437.","DOI":"10.1109\/FOCS.2016.53"},{"key":"9496_CR4","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, J.\u00a0A. Kelner, and D.\u00a0Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, 2015, pp.\u00a0143\u2013151.","DOI":"10.1145\/2746539.2746605"},{"key":"9496_CR5","unstructured":"B.\u00a0Barak and A.\u00a0Moitra, Noisy tensor completion via the sum-of-squares hierarchy, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, 2016, pp.\u00a0417\u2013445."},{"key":"9496_CR6","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, P.\u00a0Raghavendra, and D.\u00a0Steurer, Rounding semidefinite programming hierarchies via global correlation, FOCS, 2011, pp.\u00a0472\u2013481.","DOI":"10.1109\/FOCS.2011.95"},{"key":"9496_CR7","first-page":"59","volume":"21","author":"B Barak","year":"2014","unstructured":"B.\u00a0Barak and D.\u00a0Steurer, Sum-of-squares proofs and the quest toward optimal algorithms, Electronic Colloquium on Computational Complexity (ECCC) 21 (2014), 59.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"9496_CR8","unstructured":"B.\u00a0Barak and D.\u00a0Steurer, Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016, Published online."},{"key":"9496_CR9","doi-asserted-by":"crossref","unstructured":"M.\u00a0H. Bateni, M.\u00a0Charikar, and V.\u00a0Guruswami, Maxmin allocation via degree lower-bounded arborescences, STOC, 2009, pp.\u00a0543\u2013552.","DOI":"10.1145\/1536414.1536488"},{"key":"9496_CR10","doi-asserted-by":"crossref","unstructured":"A.\u00a0Ben-Tal and A.\u00a0Nemirovski, Lectures on modern convex optimization. Analysis, algorithms, and engineering applications., vol.\u00a02, Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics; Philadelphia, PA: MPS, Mathematical Programming Society, 2001.","DOI":"10.1137\/1.9780898718829"},{"issue":"1","key":"9496_CR11","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BF02771790","volume":"153","author":"G Blekherman","year":"2006","unstructured":"G.\u00a0Blekherman, There are significantly more nonegative polynomials than sums of squares, Israel Journal of Mathematics 153 (2006), no.\u00a01, 355\u2013380.","journal-title":"Israel Journal of Mathematics"},{"issue":"1\u20132","key":"9496_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-016-0998-2","volume":"161","author":"V Chandrasekaran","year":"2017","unstructured":"V.\u00a0Chandrasekaran and P.\u00a0Shah, Relative entropy optimization and its applications, Math. Program. 161 (2017), no.\u00a01-2, 1\u201332.","journal-title":"Math. Program."},{"issue":"1","key":"9496_CR13","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1287\/moor.1060.0212","volume":"32","author":"KKH Cheung","year":"2007","unstructured":"K.\u00a0K.\u00a0H. Cheung, Computation of the Lasserre ranks of some polytopes, Math. Oper. Res. 32 (2007), no.\u00a01, 88\u201394.","journal-title":"Math. Oper. Res."},{"key":"9496_CR14","doi-asserted-by":"crossref","unstructured":"E.\u00a0Chlamtac, Approximation algorithms using hierarchies of semidefinite programming relaxations, FOCS, 2007, pp.\u00a0691\u2013701.","DOI":"10.1109\/FOCS.2007.72"},{"key":"9496_CR15","doi-asserted-by":"crossref","unstructured":"E.\u00a0Chlamtac and G.\u00a0Singh, Improved approximation guarantees through higher levels of SDP hierarchies, APPROX-RANDOM, 2008, pp.\u00a049\u201362.","DOI":"10.1007\/978-3-540-85363-3_5"},{"key":"9496_CR16","doi-asserted-by":"crossref","unstructured":"E.\u00a0Chlamtac and M.\u00a0Tulsiani, Convex relaxations and integrality gaps, to appear in Handbook on semidefinite, conic and polynomial optimization, Springer, 2012.","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"9496_CR17","doi-asserted-by":"crossref","unstructured":"D.A. Cox and J.\u00a0Little\u00a0D. O\u2019Shea, Ideals, varieties, and algorithms, fourth ed., Undergraduate Texts in Mathematics, Springer, Cham, 2015, An introduction to computational algebraic geometry and commutative algebra.","DOI":"10.1007\/978-3-319-16721-3"},{"key":"9496_CR18","doi-asserted-by":"crossref","unstructured":"M.\u00a0Cygan, F.\u00a0Grandoni, and M.\u00a0Mastrolilli, How to sell hyperedges: The hypermatching assignment problem, SODA, 2013, pp.\u00a0342\u2013351.","DOI":"10.1137\/1.9781611973105.25"},{"issue":"4","key":"9496_CR19","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E de Klerk","year":"2002","unstructured":"E.\u00a0de Klerk and D.V. Pasechnik, Approximation of the stability number of a graph via copositive programming., SIAM J. Optim. 12 (2002), no.\u00a04, 875\u2013892.","journal-title":"SIAM J. Optim."},{"key":"9496_CR20","unstructured":"W.\u00a0F. de\u00a0la Vega and C.\u00a0Kenyon-Mathieu, Linear programming relaxations of maxcut, SODA, 2007, pp.\u00a053\u201361."},{"key":"9496_CR21","unstructured":"T.\u00a0de\u00a0Wolff, Amoebas, nonnegative polynomials and sums of squares supported on circuits, Oberwolfach Rep. (2015), no.\u00a023, 53\u201356."},{"issue":"1","key":"9496_CR22","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1137\/16M1086303","volume":"1","author":"M Dressler","year":"2017","unstructured":"M.\u00a0Dressler, S.\u00a0Iliman, and T.\u00a0de\u00a0Wolff, A Positivstellensatz for Sums of Nonnegative Circuit Polynomials, SIAM J. Appl. Algebra Geom. 1 (2017), no.\u00a01, 536\u2013555.","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"6","key":"9496_CR23","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"M.\u00a0X. Goemans and D.\u00a0P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no.\u00a06, 1115\u20131145.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9496_CR24","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00037-001-8192-0","volume":"10","author":"D Grigoriev","year":"2001","unstructured":"D.\u00a0Grigoriev, Complexity of positivstellensatz proofs for the knapsack, Comput. Complexity 10 (2001), no.\u00a02, 139\u2013154.","journal-title":"Comput. Complexity"},{"key":"9496_CR25","doi-asserted-by":"crossref","unstructured":"D.\u00a0Grigoriev, E.\u00a0A. Hirsch, and D.\u00a0V. Pasechnik, Complexity of semi-algebraic proofs, STACS, 2002, pp.\u00a0419\u2013430.","DOI":"10.1007\/3-540-45841-7_34"},{"issue":"1\u20133","key":"9496_CR26","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0168-0072(01)00055-0","volume":"113","author":"D Grigoriev","year":"2001","unstructured":"D.\u00a0Grigoriev and N.\u00a0Vorobjov, Complexity of null-and positivstellensatz proofs, Ann. Pure App. Logic 113 (2001), no.\u00a01-3, 153\u2013160.","journal-title":"Ann. Pure App. Logic"},{"key":"9496_CR27","doi-asserted-by":"crossref","unstructured":"M.\u00a0Gr\u00f6tschel, L.\u00a0Lov\u00e1sz, and A.\u00a0Schrijver, Geometric Algorithms and Combinatorial Optimization, vol.\u00a02, Springer, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"9496_CR28","doi-asserted-by":"crossref","unstructured":"V.\u00a0Guruswami and A.\u00a0K. Sinop, Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives, FOCS, 2011, pp.\u00a0482\u2013491.","DOI":"10.1109\/FOCS.2011.36"},{"key":"9496_CR29","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/BF01443605","volume":"32","author":"D Hilbert","year":"1888","unstructured":"D.\u00a0Hilbert, \u00dcber die Darstellung definiter Formen als Summe von Formenquadraten, Annals of Mathematics 32 (1888), 342\u2013350.","journal-title":"Annals of Mathematics"},{"key":"9496_CR30","doi-asserted-by":"crossref","unstructured":"S.\u00a0B. Hopkins, T.\u00a0Schramm, J.\u00a0Shi, and D.\u00a0Steurer, Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, 2016, pp.\u00a0178\u2013191.","DOI":"10.1145\/2897518.2897529"},{"key":"9496_CR31","doi-asserted-by":"publisher","first-page":"3:9","DOI":"10.1186\/s40687-016-0052-2","volume":"3","author":"S. Iliman","year":"2016","unstructured":"S.\u00a0Iliman and T.\u00a0de\u00a0Wolff, Amoebas, nonnegative polynomials and sums of squares supported on circuits, Res. Math. Sci. 3 (2016), 3:9.","journal-title":"Res. Math. Sci."},{"issue":"1","key":"9496_CR32","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"L.G. Khachiyan, Polynomial algorithms in linear programming, USSR Computational Mathematics and Mathematical Physics 20 (1980), no.\u00a01, 53 \u2013 72.","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"key":"9496_CR33","doi-asserted-by":"crossref","unstructured":"P.\u00a0K. Kothari, R.\u00a0Mori, R.\u00a0O\u2019Donnell, and D.\u00a0Witmer, Sum of squares lower bounds for refuting any CSP, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 2017, pp.\u00a0132\u2013145.","DOI":"10.1145\/3055399.3055485"},{"key":"9496_CR34","doi-asserted-by":"crossref","unstructured":"P.\u00a0K. Kothari, J.\u00a0Steinhardt, and D.\u00a0Steurer, Robust moment estimation and improved clustering via sum of squares, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, 2018.","DOI":"10.1145\/3188745.3188970"},{"key":"9496_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70628-1","volume-title":"Computational commutative algebra. 1","author":"M Kreuzer","year":"2000","unstructured":"M.\u00a0Kreuzer and L.\u00a0Robbiano, Computational commutative algebra. 1, Springer-Verlag, Berlin, 2000."},{"key":"9496_CR36","doi-asserted-by":"crossref","unstructured":"A.\u00a0Kurpisz, S.\u00a0Lepp\u00e4nen, and M.\u00a0Mastrolilli, Sum-of-squares hierarchy lower bounds for symmetric formulations, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Li\u00e8ge, Belgium, June 1-3, 2016, Proceedings, 2016, pp.\u00a0362\u2013374.","DOI":"10.1007\/978-3-319-33461-5_30"},{"issue":"1","key":"9496_CR37","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1287\/moor.2016.0797","volume":"42","author":"A Kurpisz","year":"2017","unstructured":"A.\u00a0Kurpisz, S.\u00a0Lepp\u00e4nen, and M.\u00a0Mastrolilli, On the hardest problem formulations for the 0\/1 lasserre hierarchy, Math. Oper. Res. 42 (2017), no.\u00a01, 135\u2013143.","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"9496_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-016-1102-7","volume":"166","author":"A Kurpisz","year":"2017","unstructured":"A.\u00a0Kurpisz, S.\u00a0Lepp\u00e4nen, and M.\u00a0Mastrolilli, An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem, Math. Program. 166 (2017), no.\u00a01-2, 1\u201317.","journal-title":"Math. Program."},{"key":"9496_CR39","doi-asserted-by":"crossref","unstructured":"J.B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000\/01), no.\u00a03, 796\u2013817.","DOI":"10.1137\/S1052623400366802"},{"issue":"3","key":"9496_CR40","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"M.\u00a0Laurent, A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res. 28 (2003), no.\u00a03, 470\u2013496.","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9496_CR41","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"M.\u00a0Laurent, Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope, Math. Oper. Res. 28 (2003), no.\u00a04, 871\u2013883.","journal-title":"Math. Oper. Res."},{"key":"9496_CR42","doi-asserted-by":"crossref","unstructured":"M.\u00a0Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp.\u00a0157\u2013270.","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"9496_CR43","doi-asserted-by":"crossref","unstructured":"J.\u00a0R. Lee, P.\u00a0Raghavendra, and D.\u00a0Steurer, Lower bounds on the size of semidefinite programming relaxations, STOC, 2015, pp.\u00a0567\u2013576.","DOI":"10.1145\/2746539.2746599"},{"key":"9496_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"L.\u00a0Lov\u00e1sz, On the shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1\u20137.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9496_CR45","doi-asserted-by":"crossref","unstructured":"A.\u00a0Magen and M.\u00a0Moharrami, Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy, APPROX-RANDOM, 2009, pp.\u00a0258\u2013271.","DOI":"10.1007\/978-3-642-03685-9_20"},{"key":"9496_CR46","doi-asserted-by":"crossref","unstructured":"M.\u00a0Mastrolilli, High degree sum of squares proofs, bienstock-zuckerberg hierarchy and CG cuts, Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, 2017, pp.\u00a0405\u2013416.","DOI":"10.1007\/978-3-319-59250-3_33"},{"key":"9496_CR47","doi-asserted-by":"crossref","unstructured":"R.\u00a0Meka, A.\u00a0Potechin, and A.\u00a0Wigderson, Sum-of-squares lower bounds for planted clique, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, 2015, pp.\u00a087\u201396.","DOI":"10.1145\/2746539.2746600"},{"key":"9496_CR48","unstructured":"T.S. Motzkin, The arithmetic-geometric inequality, Symposium on Inequalities (1967), 205\u2013224, cited By 1."},{"key":"9496_CR49","unstructured":"Y.\u00a0Nesterov, Global quadratic optimization via conic relaxation, pp.\u00a0363\u2013384, Kluwer Academic Publishers, 2000."},{"key":"9496_CR50","unstructured":"R.\u00a0O\u2019Donnell, SOS is not obviously automatizable, even approximately, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, 2017, pp.\u00a059:1\u201359:10."},{"key":"9496_CR51","doi-asserted-by":"crossref","unstructured":"J.\u00a0Oxley, Matroid theory, Oxford Graduate Texts in Mathematics, vol.\u00a02, Oxford University Press, 2011.","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"9496_CR52","unstructured":"P.\u00a0Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, PhD thesis, California Institute of Technology, 2000."},{"key":"9496_CR53","unstructured":"A.\u00a0Potechin and D.\u00a0Steurer, Exact tensor completion with sum-of-squares, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, 2017, pp.\u00a01619\u20131673."},{"issue":"3","key":"9496_CR54","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"M.\u00a0Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no.\u00a03, 969\u2013984.","journal-title":"Indiana Univ. Math. J."},{"key":"9496_CR55","doi-asserted-by":"crossref","unstructured":"P.\u00a0Raghavendra and N.\u00a0Tan, Approximating csps with global cardinality constraints using sdp hierarchies, SODA, 2012, pp.\u00a0373\u2013387.","DOI":"10.1137\/1.9781611973099.33"},{"key":"9496_CR56","unstructured":"P.\u00a0Raghavendra and B.\u00a0Weitz, On the bit complexity of sum-of-squares proofs, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, 2017, pp.\u00a080:1\u201380:13."},{"issue":"3","key":"9496_CR57","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF01442738","volume":"283","author":"B Reznick","year":"1989","unstructured":"B.\u00a0Reznick, Forms derived from the arithmetic-geometric inequality, Math. Ann. 283 (1989), no.\u00a03, 431\u2013464.","journal-title":"Math. Ann."},{"key":"9496_CR58","doi-asserted-by":"crossref","unstructured":"B.\u00a0Reznick, Some concrete aspects of Hilbert\u2019s 17th Problem, Real algebraic geometry and ordered structures (Baton Rouge, LA, 1996), Contemp. Math., vol. 253, Amer. Math. Soc., Providence, RI, 2000, pp.\u00a0251\u2013272.","DOI":"10.1090\/conm\/253\/03936"},{"key":"9496_CR59","unstructured":"T.\u00a0Schramm and D.\u00a0Steurer, Fast and robust tensor decomposition with applications to dictionary learning, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, 2017, pp.\u00a01760\u20131793."},{"issue":"6","key":"9496_CR60","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/BF01070233","volume":"23","author":"N Shor","year":"1987","unstructured":"N.\u00a0Shor, Class of global minimum bounds of polynomial functions, Cybernetics 23 (1987), no.\u00a06, 731\u2013734.","journal-title":"Cybernetics"},{"key":"9496_CR61","doi-asserted-by":"crossref","unstructured":"J.\u00a0Thapper and S.\u00a0Zivny, The limits of SDP relaxations for general-valued csps, 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, 2017, pp.\u00a01\u201312.","DOI":"10.1109\/LICS.2017.8005087"},{"key":"9496_CR62","unstructured":"G.M. Ziegler, Lectures on polytopes, Springer Verlag, 2007."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09496-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09496-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09496-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T17:08:36Z","timestamp":1649869716000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09496-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,6]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9496"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09496-x","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,6]]},"assertion":[{"value":"30 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}