2020/09/03 by Mrinalkanti Ghosh, Ghosh, Mrinalkanti, Fernando Granha Jeronimo +7 · 1 citation
Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Reliability and Maintenance Optimization
paper · pdf · doi:10.48550/arxiv.2009.01874
openalex publication_date 2020/09/03 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming\nmeta-algorithm that captures state-of-the-art polynomial time guarantees for\nmany optimization problems such as Max-k-CSPs and Tensor PCA. On the flip\nside, a SoS lower bound provides evidence of hardness, which is particularly\nrelevant to average-case problems for which NP-hardness may not be available.\n In this paper, we consider the following average case problem, which we call\nthe \Planted Affine Planes (PAP) problem: Given m random vectors\nd1,\…,dm in \ℝn, can we prove that there is no vector v \∈\n\ℝn such that for all u \∈ [m], \⟨ v, du\⟩2 = 1? In\nother words, can we prove that m random vectors are not all contained in two\nparallel hyperplanes at equal distance from the origin? We prove that for m\n\≤ n3/2-\ε, with high probability, degree-n\Ω(\ε)\nSoS fails to refute the existence of such a vector v.\n When the vectors d1,\…,dm are chosen from the multivariate normal\ndistribution, the PAP problem is equivalent to the problem of proving that a\nrandom n-dimensional subspace of \ℝm does not contain a boolean\nvector. As shown by Mohanty--Raghavendra--Xu [STOC 2020], a lower bound for\nthis problem implies a lower bound for the problem of certifying energy upper\nbounds on the Sherrington-Kirkpatrick Hamiltonian, and so our lower bound\nimplies a degree-n\Ω(\ε) SoS lower bound for the certification\nversion of the Sherrington-Kirkpatrick problem.\n