All reports by Author Suprovat Ghoshal:

__
TR19-161
| 13th November 2019
__

Suprovat Ghoshal, Rishi Saket#### Hardness of Learning DNFs using Halfspaces

__
TR19-115
| 4th September 2019
__

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx#### Parameterized Intractability of Even Set and Shortest Vector Problem

__
TR19-079
| 28th May 2019
__

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka#### Average Bias and Polynomial Sources

Revisions: 2

__
TR18-057
| 26th March 2018
__

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi#### Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

__
TR17-115
| 5th July 2017
__

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket#### Hardness of learning noisy halfspaces using polynomial thresholds

__
TR15-193
| 26th November 2015
__

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket#### On the hardness of learning sparse parities

Suprovat Ghoshal, Rishi Saket

The problem of learning $t$-term DNF formulas (for $t = O(1)$) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A $t$-term DNF can be efficiently learnt using a $t$-term DNF only if $t = 1$ i.e., when it is an AND, while even ... more >>>

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

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 $d \in \mathbb{Z}^+$ and $\epsilon > 0$, it is NP-hard to decide: given a set of $\{-1,1\}$-labeled points in $\mathbb{R}^n$ whether (YES Case) ... more >>>

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{F}_2$ on $n$ variables, decide if there exists a nonzero solution of Hamming weight at most $k$ (i.e. a $k$-sparse solution). While ... more >>>