Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x\in {\mathbb{R}}^n$ that maximize…