SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

• 成果类型: Article; Early Access
• 署名作者: Kurpisz, Adam; Potechin, Aaron; Wirth, Elias
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Chicago; Technical University of Berlin
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0422
• 发表日期: 2025
• 关键词: sherali-adams relaxations; of-squares proofs; graph isomorphism; tensor decomposition; maximum cut; algorithms; SUM; complexity; number; POLYNOMIALS

摘要

We introduce several methods to study the rank of the sum of squares (SoS) hierarchy for problems over the Boolean hypercube. We apply our techniques to improve upon existing results, thus answering several open questions. We answer the question by Laurent regarding the SoS rank of the empty integral hull (EIH) problem. We prove that the SoS rank is between inverted right perpendicularn/2inverted left perpendicular and inverted right perpendicularn/2+ root n log 2ninverted left perpendicular. We refute the Lee-Prakash-de Wolf-Yuen (LPdWY) conjecture for the SoS rank of symmetric quadratic functions in n variables with roots placed in points k - 1 and k that conjectured the lower bound of ohm(n). We prove that O(root nk log (n)). We answer another question by Laurent for an instance of the min knapsack problem parameterized by P. We prove a nearly tight SoS rank between ohm(root n log P) and O(root n log P).Finally, we refute the conjecture by Bienstock-Zuckerberg that presumed the SoS rank lower bound of n/4 for an instance of the set cover problem. We refute the conjecture by providing an O(root n log(n)) SoS certifin cate for this problem.