Browsing by Author "Nelson, Jelani"
Now showing items 1-20 of 29
-
Almost Optimal Explicit Johnson-Lindenstrauss Families
Kane, Daniel; Meka, Raghu; Nelson, Jelani (Springer Science + Business Media, 2011)The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson Lindenstrauss property ... -
Bounded Independence Fools Degree-2 Threshold Functions
Diakonikolas, Ilias; Kane, Daniel M.; Nelson, Jelani (IEEE, 2010)For an n-variate degree-2 real polynomial p, we prove that \(E_{x\sim D}[sig(p(x))]\) Is determined up to an additive \(\epsilon\) as long as D is a k-wise Independent distribution over \(\{-1, 1\}^n\) for \(k = ... -
BPTree: An ℓ2 Heavy Hitters Algorithm Using Constant Memory
Braverman, Vladimir; Chestnut, Stephen R.; Ivkin, Nikita; Nelson, Jelani; Wang, Zhengyu; Woodruff, David P. (2017)The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list i1,i2,...,im∈[n] and the goal is to identify the items among [n] that appear frequently ... -
Cache-Oblivious Streaming B-Trees
Bender, Michael A.; Farach-Colton, Martin; Fineman, Jeremy T.; Fogel, Yonatan R.; Kuszmaul, Bradley C.; Nelson, Jelani (Association for Computer Machinery, 2007)A streaming B-tree is a dictionary that efficiently implements insertions and range queries. We present two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious lookahead array (COLA). For block-transfer ... -
Chaining Introduction With Some Computer Science Applications
Nelson, Jelani (European Association for Theoretical Computer Science, 2016) -
A Derandomized Sparse Johnson-Lindenstrauss Transform
Kane, Daniel M.; Nelson, Jelani (2010)Recent work of [Dasgupta-Kumar-Sarl´os, 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 ... -
Dynamic ham-sandwich cuts in the plane
Abbott, Timothy G.; Burr, Michael A.; Chan, Timothy M.; Demaine, Erik D.; Demaine, Martin L.; Hugg, John; Kane, Daniel; Langerman, Stefan; Nelson, Jelani; Rafalin, Eynat; Seyboth, Kathryn; Yeung, Vincent (Elsevier BV, 2009)We design efficient data structures for dynamically maintaining a ham-sandwich cut of two point sets in the plane subject to insertions and deletions of points in either set. A ham-sandwich cut is a line that simultaneously ... -
Fast Manhattan sketches in data streams
Nelson, Jelani; Woodruff, David P. (ACM, 2010)The ℓ1-distance, also known as the Manhattan or taxicab distance, between two vectors x, y in R n is Pn |xi − yi|. i=1 Approximating this distance is a fundamental primitive on massive databases, with applications to ... -
Fast Moment Estimation in Data Streams in Optimal Space
Kane, Daniel M.; Nelson, Jelani; Porat, Ely; Woodruff, David P. (ACM, 2011)We give a space-optimal streaming algorithm with update time \(O(log^2(1/\epsilon)loglog(1/\epsilon))\) for approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream up to a factor ... -
Heavy Hitters via Cluster-Preserving Clustering
Larsen, Kasper Green; Nelson, Jelani; Nguyen, Huy L.; Thorup, Mikkel (IEEE, 2016-10)In the turnstile ℓp heavy hitters problem with parameter ε, one must maintain a high-dimensional vector x ∈ ℝn subject to updates of the form update (i,Δ) causing the change xi ← xi + Δ, where i ε[n], Δ ∈ ℝ. Upon receiving ... -
An improved analysis of the ER-SpUD dictionary learning algorithm
Blasiok, Jaroslaw; Nelson, Jelani (2016)In "dictionary learning" we observe Y=AX+E for some Y∈ℝn×p, A∈ℝm×n, and X∈ℝm×p. The matrix Y is observed, and A,X,E are unknown. Here E is "noise" of small norm, and X is column-wise sparse. The matrix A is referred to as ... -
The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction
Larsen, Kasper Green; Nelson, Jelani (2014)For any n>1 and \(0<\epsilon<1/2\), we show the existence of an \(n^{O(1)}\)-point subset X of \(\mathbb{R}^n\) such that any linear map from \((X,\ell_2)\) to \(\ell^m_2\) with distortion at most \(1+\epsilon\) must have ... -
Lower Bounds for Oblivious Subspace Embeddings
Nelson, Jelani; Nguyễn, Huy L. (Springer, 2014)An oblivious subspace embedding (OSE) for some \(\epsilon\),\(\delta \in (0,1/3)\) and d ≤ m ≤ n is a distribution \(\mathcal{D}\) over \(\mathbb{R}^{m×n}\) such that \(\underset {\Pi \sim \mathcal{D}} {Pr} (\forall x \in ... -
A Near-Optimal Algorithm for L1-Difference
Nelson, Jelani; Woodruff, David P (2009)We give the first L1-sketching algorithm for integer vectors which produces nearly optimal sized sketches in nearly linear time. This answers the first open problem in the list of open problems from the 2006 IITK Workshop ... -
New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows
Nelson, Jelani; Price, Eric; Wootters, Mary (Society for Industrial and Applied Mathematics, 2014)In this paper, we present novel constructions of matrices with the restricted isometry property (RIP) that support fast matrix-vector multiplication. Our guarantees are the best known, and can also be used to obtain the ... -
A Note on Reductions Between Compressed Sensing Guarantees
Morgan, Tom; Nelson, Jelani (IEEE, 2016)In compressed sensing, one wishes to acquire an approximately sparse high-dimensional signal x∈ℝn via m≪n noisy linear measurements, then later approximately recover x given only those measurement outcomes. Various guarantees ... -
A Note on Set Cover Inapproximability Independent of Universe Size
Nelson, Jelani (Hasso-Plattner-Institut, 2007)In the set cover problem we are given a collection of m sets whose union covers [n]=1n and must find a minimum-sized subcollection whose union still covers [n]. We investigate the approximability of set cover by an ... -
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
Nelson, Jelani; Nguyẽn, Huy L.; Woodruff, David P. (Elsevier, 2014)We study classic streaming and sparse recovery problems using deterministic linear sketches, including \(\ell_1/\ell_1\) and \(\ell_{\infty}/\ell_1\) sparse recovery problems (the latter also being known as ℓ1ℓ1-heavy ... -
On the Exact Space Complexity of Sketching and Streaming Small Norms
Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (Society for Industrial and Applied Mathematics, 2010)We settle the 1-pass space complexity of \((1 \pm \epsilon)\)-approximating the \(L_p\) norm, for real p with 1 ≤ p ≤ 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the ... -
An Optimal Algorithm for the Distinct Elements Problem
Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (ACM, 2010)We give the first optimal algorithm for estimating the number of distinct elements in a data stream, closing a long line of theoretical research on this problem begun by Flajolet and Martin in their seminal paper in FOCS ...