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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>