All reports by Author Jelani Nelson:

__
TR18-129
| 13th July 2018
__

Jelani Nelson, Huacheng Yu#### Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Revisions: 1

__
TR10-098
| 17th June 2010
__

Daniel Kane, Jelani Nelson#### A Derandomized Sparse Johnson-Lindenstrauss Transform

Revisions: 2

__
TR09-117
| 18th November 2009
__

Ilias Diakonikolas, Daniel Kane, Jelani Nelson#### Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

__
TR07-105
| 21st September 2007
__

Jelani Nelson#### A Note on Set Cover Inapproximability Independent of Universe Size

Revisions: 1

Jelani Nelson, Huacheng Yu

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the ... more >>>

Daniel Kane, Jelani Nelson

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

Ilias Diakonikolas, Daniel Kane, Jelani Nelson

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

Jelani Nelson

In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for ... more >>>