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