5 citations · 8 across the 14 of their papers we have counts for
6 papers · 1 filter
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]…