5 citations · 8 across the 14 of their papers we have counts for
22 papers
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…
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits
Suprovat Ghoshal, Aadirupa Saha
We introduce the \emph{Correlated Preference Bandits} problem with random utility-based choice models (RUMs), where the goal is to identify the best item from a given pool of i…
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…
Combinatorial lower bounds for 3-query LDCs
Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal
A code is called a -query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index and a received word close to an encoding of a mes…
Hardness of Learning DNFs using Halfspaces
Suprovat Ghoshal, Rishi Saket
The problem of learning -term DNF formulas (for ) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A -term DNF can be ef…
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
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…
Average Bias and Polynomial Sources
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal +1
We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution over , its average bias is: $b_{\text{av}}(…
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]…
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. +1
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
Hardness of learning noisy halfspaces using polynomial thresholds
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs). In particular, we prove that for any constants…
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…
On the hardness of learning sparse parities
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal +1
This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equa…