5 citations · 8 across the 14 of their papers we have counts for
14 papers · 1 filter
Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs
Rares-Darius Buhai, Suprovat Ghoshal, Pravesh Kothari +4
We give a polynomial-time algorithm that achieves an -approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most constrain…
Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
We describe an -improvement over threshold rounding schemes for a broad class of Boolean MAX 2-CSP instances in which every variable appears in at most cons…
Max Cut with Small-Dimensional SDP Solutions
Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee
We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyper…
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
Max-Cut is a classical graph-partitioning problem where given a graph , the objective is to find a cut which maximizes the number of edges crossing the cut. In…
Constraint Satisfaction Problems with Advice
Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
We initiate the study of algorithms for constraint satisfaction problems with ML oracle advice. We introduce two models of advice and then design approximation algorithms for Max C…
New Approximation Bounds for Small-Set Vertex Expansion
Suprovat Ghoshal, Anand Louis
The vertex expansion of the graph is a fundamental graph parameter. Given a graph and a parameter , its -Small-Set Vertex Expansion (SSVE) is defined as…
A PTAS for -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 and an integer , and the goal is to find a matrix of…
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 where the objective is to find a labeling of relative weight ex…
Approximating CSPs with Outliers
Suprovat Ghoshal, Anand Louis
Constraint satisfaction problems (CSPs) are ubiquitous in theoretical computer science. We study the problem of StrongCSPs, i.e. instances where a large induced sub-instance has a…
A Characterization of Approximability for Biased CSPs
Suprovat Ghoshal, Euiwoong Lee
A -biased Max-CSP instance with predicate is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative…
Approximation Algorithms and Hardness for Strong Unique Games
Suprovat Ghoshal, Anand Louis
The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subse…
Approximation Algorithms for Partially Colorable Graphs
Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For and $k \in \m…
Tight Approximation Bounds for Maximum Multi-Coverage
Siddharth Barman, Omar Fawzi, Suprovat Ghoshal +1
In the classic maximum coverage problem, we are given subsets of a universe along with an integer and the objective is to find a subset $S \subseteq [m]…
Testing Sparsity over Known and Unknown Bases
Siddharth Barman, Arnab Bhattacharyya, Suprovat Ghoshal
Sparsity is a basic property of real vectors that is exploited in a wide variety of applications. In this work, we describe property testing algorithms for sparsity that observe a…