1 citations · 1 across the 12 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…
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}}(…
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…