2 papers
cs.CC2020
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones +2
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-algorithm that captures state-of-the-art polynomial time guarantees for many optimization problems such as Ma…
cs.CC2019
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Chris Jones, Matt McPartlon
Inspired by the boolean discrepancy problem, we study the following optimization problem which we term \textsc{Spherical Discrepancy}: given unit vectors , fin…