2 citations · 8 across the 7 of their papers we have counts for
4 papers · 1 filter
Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
Mrinalkanti Ghosh
This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dic…
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…
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…
From Weak to Strong LP Gaps for all CSPs
Mrinalkanti Ghosh, Madhur Tulsiani
We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP…