Suprovat Ghoshal

collaborators

2 papers

cs.DS2023

A PTAS for $ℓ_{0}$ -Low Rank Approximation: Solving Dense CSPs over Reals

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4

We consider the Low Rank Approximation problem, where the input consists of a matrix $A \in R^{n_{R} \times n_{C}}$ and an integer $k$ , and the goal is to find a matrix $B$ of…

cs.DS2023

On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

Suprovat Ghoshal, Euiwoong Lee

A $μ$ -constrained Boolean Max-CSP $(ψ)$ instance is a Boolean Max-CSP instance on predicate $ψ : {0, 1}^{r} \to {0, 1}$ where the objective is to find a labeling of relative weight ex…

A PTAS for ℓ0​-Low Rank Approximation: Solving Dense CSPs over Reals

On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

A PTAS for $ℓ_{0}$ -Low Rank Approximation: Solving Dense CSPs over Reals