3 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.DS2018
Approximating Operator Norms via Generalized Krivine Rounding
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We consider the -Grothendieck problem, which seeks to maximize the bilinear form for an input matrix over vectors with . The…
cs.CC2018
Inapproximability of Matrix Norms
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We study the problem of computing the norm of a matrix , defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac…