1 citations · 1 across the 5 of their papers we have counts for
11 papers
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…