ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > DANIEL KANE:
All reports by Author Daniel Kane:

TR10-098 | 17th June 2010
Daniel Kane, Jelani Nelson

A Derandomized Sparse Johnson-Lindenstrauss Transform

Revisions: 2

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in ... more >>>


TR09-117 | 18th November 2009
Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>




ISSN 1433-8092 | Imprint