All reports by Author Rishi Saket:

__
TR19-161
| 13th November 2019
__

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

__
TR17-147
| 3rd October 2017
__

Venkatesan Guruswami, Rishi Saket#### Hardness of Rainbow Coloring Hypergraphs

__
TR17-115
| 5th July 2017
__

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

__
TR16-116
| 26th July 2016
__

Subhash Khot, Rishi Saket#### Approximating CSPs using LP Relaxation

__
TR15-193
| 26th November 2015
__

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

__
TR14-051
| 12th April 2014
__

Subhash Khot, Rishi Saket#### Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

__
TR13-071
| 8th May 2013
__

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket#### Inapproximability of Minimum Vertex Cover on $k$-uniform $k$-partite Hypergraphs

__
TR10-177
| 16th November 2010
__

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu#### Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

__
TR07-073
| 3rd August 2007
__

Parikshit Gopalan, Subhash Khot, Rishi Saket#### Hardness of Reconstructing Multivariate Polynomials over Finite Fields

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

Venkatesan Guruswami, Rishi Saket

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

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

Subhash Khot, Rishi Saket

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

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

Subhash Khot, Rishi Saket

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

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

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

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

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

Parikshit Gopalan, Subhash Khot, Rishi Saket

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