{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:09Z","timestamp":1771623789536,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy \u00f0 The Berlin Mathematics Research Center MATH+","award":["EXC-2046\/1, project ID 390685689, BMS Stipend"],"award-info":[{"award-number":["EXC-2046\/1, project ID 390685689, BMS Stipend"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,24]]},"DOI":"10.1145\/3597066.3597098","type":"proceedings-article","created":{"date-parts":[[2023,7,5]],"date-time":"2023-07-05T18:15:27Z","timestamp":1688580927000},"page":"443-451","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Sum of Squares Bounds for the Empty Integral Hull Problem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2320-4482","authenticated-orcid":false,"given":"Adam","family":"Kurpisz","sequence":"first","affiliation":[{"name":"BFH, Switzerland and ETH, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8957-8736","authenticated-orcid":false,"given":"Elias","family":"Wirth","sequence":"additional","affiliation":[{"name":"TU Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Expander flows, geometric embeddings and graph partitioning. JACM 56, 2","author":"Arora S.","year":"2009","unstructured":"S. Arora, S. Rao, and U.\u00a0V. Vazirani. 2009. Expander flows, geometric embeddings and graph partitioning. JACM 56, 2 (2009), 5:1\u20135:37."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.53"},{"key":"e_1_3_2_1_3_1","volume-title":"STOC 2015","author":"Barak B.","year":"2015","unstructured":"B. Barak, J.\u00a0A. Kelner, and D. Steurer. 2015. Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. In STOC 2015, Portland, OR, USA, June 14-17, 2015. 143\u2013151."},{"key":"e_1_3_2_1_4_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\u2013445."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"B. Barak P. Raghavendra and D. Steurer. 2011. Rounding Semidefinite Programming Hierarchies via Global Correlation. In FOCS. 472\u2013481.","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Aditya Bhaskara Moses Charikar Aravindan Vijayaraghavan Venkatesan Guruswami and Yuan Zhou. 2012. Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. In SODA.","DOI":"10.1137\/1.9781611973099.34"},{"key":"e_1_3_2_1_7_1","volume-title":"Convex optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0212"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.1.19.10593"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45535-3_6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0983"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09496-x"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00093"},{"key":"e_1_3_2_1_14_1","first-page":"796","article-title":"When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?Math","volume":"26","author":"Goemans X.","year":"2001","unstructured":"M.\u00a0X. Goemans and L. Tun\u00e7el. 2001. When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?Math. Oper. Res. 26, 4 (2001), 796\u2013815.","journal-title":"Oper. Res."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8192-0"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45841-7_34"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"V. Guruswami and A.\u00a0K. Sinop. 2011. Lasserre Hierarchy Higher Eigenvalues and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. In FOCS. 482\u2013491.","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_1_22_1","volume-title":"Sum-of-Squares Lower Bounds for Sparse Independent Set. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021","author":"Jones Chris","year":"2021","unstructured":"Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, and Jeff Xu. 2021. Sum-of-Squares Lower Bounds for Sparse Independent Set. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. 406\u2013416."},{"key":"e_1_3_2_1_23_1","volume-title":"Hypercontractive inequalities via SOS, with an application to Vertex-Cover. CoRR abs\/1212.5324","author":"Kauers Manuel","year":"2012","unstructured":"Manuel Kauers, Ryan O\u2019Donnell, Li-Yang Tan, and Yuan Zhou. 2012. Hypercontractive inequalities via SOS, with an application to Vertex-Cover. CoRR abs\/1212.5324 (2012). arxiv:1212.5324http:\/\/arxiv.org\/abs\/1212.5324"},{"key":"e_1_3_2_1_24_1","volume-title":"STOC","author":"Kothari P.","year":"2018","unstructured":"P. Kothari, J. Steinhardt, and D. Steurer. 2018. Robust Moment Estimation and Improved Clustering via Sum of Squares. In STOC 2018."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_26_1","volume-title":"ICALP","author":"Kurpisz Adam","year":"2019","unstructured":"Adam Kurpisz. 2019. Sum-Of-Squares Bounds via Boolean Function Analysis. In ICALP July 9-12, 2019, Patras, Greece."},{"key":"e_1_3_2_1_27_1","volume-title":"IPCO 2016, Li\u00e8ge, Belgium, June 1-3, 2016, Proceedings. 362\u2013374","author":"Kurpisz A.","unstructured":"A. Kurpisz, S. Lepp\u00e4nen, and M. Mastrolilli. 2016. Sum-of-Squares Hierarchy Lower Bounds for Symmetric Formulations. In Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Li\u00e8ge, Belgium, June 1-3, 2016, Proceedings. 362\u2013374."},{"key":"e_1_3_2_1_28_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15","author":"Kurpisz A.","year":"2016","unstructured":"A. Kurpisz, S. Lepp\u00e4nen, and M. Mastrolilli. 2016. Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. 78:1\u201378:14."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0797"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1102-7"},{"key":"e_1_3_2_1_31_1","volume-title":"ICALP 2021","author":"Kurpisz Adam","year":"2021","unstructured":"Adam Kurpisz, Aaron Potechin, and Elias\u00a0Samuel Wirth. 2021. SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. ICALP 2021 (2021)."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01549-3"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.4.871.20508"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"J.\u00a0R. Lee P. Raghavendra and D. Steurer. 2015. Lower Bounds on the Size of Semidefinite Programming Relaxations. In STOC. 567\u2013576.","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_3_2_1_36_1","volume-title":"On the Sum-of-Squares Degree of Symmetric Quadratic Functions. In 31st Conference on Computational Complexity.","author":"Lee Troy","year":"2016","unstructured":"Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. 2016. On the Sum-of-Squares Degree of Symmetric Quadratic Functions. In 31st Conference on Computational Complexity."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"e_1_3_2_1_39_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\u2013384."},{"key":"e_1_3_2_1_40_1","volume-title":"Analysis of boolean functions","author":"O\u2019Donnell Ryan","unstructured":"Ryan O\u2019Donnell. 2014. Analysis of boolean functions. Cambridge University Press."},{"key":"e_1_3_2_1_41_1","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell R.","unstructured":"R. O\u2019Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press."},{"key":"e_1_3_2_1_42_1","unstructured":"P. Parrilo. 2000. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis. California Institute of Technology."},{"key":"e_1_3_2_1_43_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\u20131673."},{"key":"e_1_3_2_1_44_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\u20131793."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01745-9"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.24"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079245"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Madhur Tulsiani. 2009. CSP gaps and reductions in the lasserre hierarchy. In STOC. 303\u2013312.","DOI":"10.1145\/1536414.1536457"}],"event":{"name":"ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023","location":"Troms\u00f8 Norway","acronym":"ISSAC 2023"},"container-title":["Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597066.3597098","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3597066.3597098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T09:36:43Z","timestamp":1755855403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597066.3597098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":49,"alternative-id":["10.1145\/3597066.3597098","10.1145\/3597066"],"URL":"https:\/\/doi.org\/10.1145\/3597066.3597098","relation":{},"subject":[],"published":{"date-parts":[[2023,7,24]]},"assertion":[{"value":"2023-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}