21 citations · 47 across the 19 of their papers we have counts for
8 papers · 1 filter
Hardness of Learning Boolean Functions from Label Proportions
Venkatesan Guruswami, Rishi Saket
In recent years the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into s…
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…
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…
On the hardness of learning sparse parities
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal +1
This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equa…
Tight Hardness of the Non-commutative Grothendieck Problem
Jop Briët, Oded Regev, Rishi Saket
We prove that for any $\eps > 0$ it is -hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$,…
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs
Rishi Saket
This work revisits the PCP Verifiers used in the works of Hastad [Has01], Guruswami et al.[GHS02], Holmerin[Hol02] and Guruswami[Gur00] for satisfiable Max-E3-SAT and Max-Ek-Set-Sp…
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
Subhash Khot, Rishi Saket
This work studies the hardness of finding independent sets in hypergraphs which are either 2-colorable or are almost 2-colorable, i.e. can be 2-colored after removing a small fract…
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
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 c…