Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes.
Mrinalkanti GhoshFernando Granha JeronimoChris JonesAaron PotechinGoutham RajendranPublished in: FOCS (2020)
Keyphrases
- lower bound
- upper bound
- branch and bound algorithm
- branch and bound
- affine transformation
- np hard
- objective function
- lower and upper bounds
- image registration
- affine invariant
- sample complexity
- planar surfaces
- online algorithms
- optimal solution
- three dimensional
- lower bounding
- randomly generated problems
- vc dimension
- worst case
- linear programming relaxation