All reports by Author YI WU:

__
TR10-006
| 11th January 2010
__

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan#### Fooling functions of halfspaces under product distributions

Revisions: 2

__
TR09-130
| 1st December 2009
__

Ryan O'Donnell, YI WU, Yuan Zhou#### Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

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 $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>