activity
20122025
most citedWeak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere

2 citations · 8 across the 7 of their papers we have counts for

collaborators
Showing 2016Show all

2 papers · 1 filter

cs.DS2016★ 2 cited

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 -variate degree- homogeneous polynomial with real coefficients, compute a unit vector that maximize…

cs.CC2016

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…