Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR09-130 | 1st December 2009
Ryan O'Donnell, YI WU, Yuan Zhou

Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

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

ISSN 1433-8092 | Imprint