3 citations · 3 across the 2 of their papers we have counts for
3 papers
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)$…
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio +1
Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness…
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O'Donnell, Yi Wu, Yuan Zhou
We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}^d under the Hamming distance. Recall that here H is said to be an (r, cr, p…