{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:06Z","timestamp":1781031426395,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Swiss National Science Foundation (SNSF)","award":["10004947"],"award-info":[{"award-number":["10004947"]}]},{"name":"Dutch Research Council (NWO)","award":["VI.Veni.242.234"],"award-info":[{"award-number":["VI.Veni.242.234"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800760","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"410-419","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hesse\u2019s Redemption: Efficient Convex Polynomial Programming"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3790-492X","authenticated-orcid":false,"given":"Lucas","family":"Slot","sequence":"first","affiliation":[{"name":"University of Amsterdam, Amsterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3908-8180","authenticated-orcid":false,"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-2365-4165","authenticated-orcid":false,"given":"Manuel","family":"Wiedmer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2024.109808"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0499-2"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110856010"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.108119"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01714-2"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the International Congress of Mathematicians\u2014Seoul","author":"Barak Boaz","year":"2014","unstructured":"Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. In Proceedings of the International Congress of Mathematicians\u2014Seoul 2014. Vol. IV. Kyung Moon Sa, Seoul, 509\u2013533. isbn:978-89-6105-807-0; 978-89-6105-803-2"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014813701864"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Grigoriy Blekherman. 2009. Convex Forms that are not Sums of Squares. Preprint https:\/\/doi.org\/10.48550\/arXiv.0910.0656 10.48550\/arXiv.0910.0656","DOI":"10.48550\/arXiv.0910.0656"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Alex Bortolotti Monaldo Mastrolilli Marilena Palomba and Luis Felipe Vargas. 2025. On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations. arxiv:2509.06928. https:\/\/doi.org\/10.48550\/ARXIV.2509.06928 arXiv:2509.06928 10.48550\/ARXIV.2509.06928","DOI":"10.48550\/ARXIV.2509.06928"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Alex Bortolotti Monaldo Mastrolilli and Luis Felipe Vargas. 2025. On the Degree Automatability of Sum-of-Squares Proofs. arxiv:2504.17756. https:\/\/doi.org\/10.48550\/ARXIV.2504.17756 arXiv:2504.17756 10.48550\/ARXIV.2504.17756","DOI":"10.48550\/ARXIV.2504.17756"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386223"},{"key":"e_1_3_2_1_13_1","volume-title":"Linear programming and extensions","author":"Dantzig George B.","unstructured":"George B. Dantzig. 1963. Linear programming and extensions. Princeton University Press, Princeton, NJ."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/15m103114x"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071b.033"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf03191214"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01442264"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597066.3597075"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"e_1_3_2_1_23_1","first-page":"117","article-title":"\u00dcber die Bedingung, unter welche eine homogene ganze Function von nunabh\u00e4ngigen Variabeln durch line\u00e4re Substitutionem von n andern unabh\u00e4ngigen Variabeln auf eine homogene Function sich zur\u00fcck-f\u00fchren l\u00e4sst, die eine Variable weniger enth\u00e4lt","volume":"42","author":"Hesse Otto","year":"1851","unstructured":"Otto Hesse. 1851. \u00dcber die Bedingung, unter welche eine homogene ganze Function von nunabh\u00e4ngigen Variabeln durch line\u00e4re Substitutionem von n andern unabh\u00e4ngigen Variabeln auf eine homogene Function sich zur\u00fcck-f\u00fchren l\u00e4sst, die eine Variable weniger enth\u00e4lt. Journal f\u00fcr die reine und angewandte Mathematik, 42 (1851), 117\u2013124.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385885"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1980.29"},{"key":"e_1_3_2_1_26_1","volume-title":"A polynomial algorithm in linear programming. Soviet Mathematics \u2013 Doklady, 1","author":"Khachiyan L. G.","year":"1979","unstructured":"L. G. Khachiyan. 1979. A polynomial algorithm in linear programming. Soviet Mathematics \u2013 Doklady, 1 (1979), 191\u2013194."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90098-1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/s1052623400366802"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00013-008-2687-8"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1964.14.243"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf02592948"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01449-1"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.59"},{"key":"e_1_3_2_1_35_1","unstructured":"M.W. Padberg and M.R. Rao. 1981. The Russian method for linear inequalities III:bounded integer programming. INRIA. https:\/\/inria.hal.science\/inria-00076483"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.7907\/2K6Y-CH43"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/21m1434945"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/a:1008203903341"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.80"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf02614433"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203021"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1273"},{"key":"e_1_3_2_1_43_1","volume-title":"Hesse\u2019s Redemption: Efficient Convex Polynomial Programming (full version). arxiv:2511.03440.","author":"Slot Lucas","year":"2025","unstructured":"Lucas Slot, David Steurer, and Manuel Wiedmer. 2025. Hesse\u2019s Redemption: Efficient Convex Polynomial Programming (full version). arxiv:2511.03440."},{"key":"e_1_3_2_1_44_1","volume-title":"Mathematical problems for the next century. La Gaceta de la Real Sociedad Matem\u00e1tica Espa\u00f1ola, 3, 3","author":"Smale Steve","year":"2000","unstructured":"Steve Smale. 2000. Mathematical problems for the next century. La Gaceta de la Real Sociedad Matem\u00e1tica Espa\u00f1ola, 3, 3 (2000), 413\u2013434. issn:1138-8927"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90100-c"},{"key":"e_1_3_2_1_46_1","first-page":"357","article-title":"Informational complexity and e\ufb00ective methods of solution of convex extremal problems","volume":"12","author":"Yudin D.","year":"1976","unstructured":"D. Yudin and A. S. Nemirovski. 1976. Informational complexity and e\ufb00ective methods of solution of convex extremal problems. Econom. Math. Methods, 12 (1976), 357\u2013369.","journal-title":"Econom. Math. Methods"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:23Z","timestamp":1781028023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":46,"alternative-id":["10.1145\/3798129.3800760","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800760","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}