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

A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be ... 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 paper studies how well the standard LP relaxation approximates a k-ary constraint satisfaction problem (CSP) on label set [L]. We show that, assuming the Unique Games Conjecture, it achieves an approximation within O(k^3\cdot \log L) of the optimal approximation factor. In particular we prove the following hardness result: let ... 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 >>>

We show that it is quasi-NP-hard to color 2-colorable 12-uniform hypergraphs with 2^{(\log n)^{\Omega(1) }} colors where n is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with 2^{2^{\Omega(\sqrt{\log \log n})}} colors. Their result is obtained by composing a ... more >>>

We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k=2), the minimum vertex cover can be computed in polynomial time. For k \ge 3, this problem is known to be NP-hard. For general k, the problem was ... more >>>

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

We study the polynomial reconstruction problem for low-degree
multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values f(x) for each of these points, with the promise that there is a polynomial over GF[2] of ... more >>>