38 citations · 171 across the 26 of their papers we have counts for
Showing 2010 · cs.CCShow all
2 papers · 2 filters
cs.CC2010
Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra +1
We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$…
cs.CC2010★ 5 cited
Reductions Between Expansion Problems
Prasad Raghavendra, David Steurer, Madhur Tulsiani
The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in gr…