A Derandomized Sparse Johnson-Lindenstrauss Transform

Daniel M. Kane, Jelani Nelson

Type: Preprint

Publication Date: 2010-01-01

Citations: 58

DOI: https://doi.org/10.48550/arxiv.1006.3585

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	A Derandomized Sparse Johnson-Lindenstrauss Transform	2010	Daniel M. Kane Jelani Nelson
+ PDF Chat	Sparser Johnson-Lindenstrauss Transforms	2012	Daniel M. Kane Jelani Nelson
+	Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing	2014	Jalaj Upadhyay
+	Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More	2024	Ce Jin Yinzhan Xu
+ PDF Chat	Fast, Deterministic and Sparse Dimensionality Reduction	2018	Daniel Dadush Cristóbal Guzmán Neil Olver
+ PDF Chat	Derandomization and absolute reconstruction for sums of powers of linear forms	2021	Pascal Koiran Mateusz Skomra
+ PDF Chat	Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime	2024	Tushant Mittal Sourya Roy
+	A Sparse Johnson-Lindenstrauss Transform using Fast Hashing	2023	Jakob Bæk Tejs Houen Mikkel Thorup
+	Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming	2023	Praneeth Kacham Rasmus Pagh Mikkel Thorup David P. Woodruff
+	Circulant Matrices and Differential Privacy.	2014	Jalaj Upadhyay
+	Circulant Matrices and Differential Privacy.	2014	Jalaj Upadhyay
+ PDF Chat	Asynchronous COMID: The Theoretic Basis for Transmitted Data Sparsification Tricks on Parameter Server	2019	Daning Cheng Shigang Li Zhang Yunquan
+ PDF Chat	Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More	2024	Ce Jin Yinzhan Xu
+	Communication Complexity (for Algorithm Designers)	2015	Tim Roughgarden
+ PDF Chat	Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions	1996	Noga Alon Moni Naor
+ PDF Chat	Communication Complexity (for Algorithm Designers)	2016	Tim Roughgarden
+ PDF Chat	Communication Complexity (for Algorithm Designers)	2016	Tim Roughgarden
+	Derandomization and absolute reconstruction for sums of powers of linear forms	2019	Pascal Koiran Mateusz Skomra
+	Derandomization and absolute reconstruction for sums of powers of linear forms	2019	Pascal Koiran Mateusz Skomra
+	Deterministic 3SUM-Hardness	2023	Nick Fischer Piotr Kaliciak Adam Polak

Works That Cite This (33)

Action	Title	Year	Authors
+	New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property	2010	Felix Krahmer Rachel Ward
+ PDF Chat	New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property	2011	Felix Krahmer Rachel Ward
+ PDF Chat	Fast, Deterministic and Sparse Dimensionality Reduction	2018	Daniel Dadush Cristóbal Guzmán Neil Olver
+	Embeddings of Schatten Norms with Applications to Data Streams	2017	Yi Li David P. Woodruff
+ PDF Chat	Randomized Algorithms for Matrices and Data	2012	Michael W. Mahoney
+ PDF Chat	Optimal Rip Matrices with Slightly Less Randomness	2024	Shravas Rao
+ PDF Chat	OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings	2013	Jelani Nelson Huy L. Nguyễn
+	Deterministic parallel algorithms for bilinear objective functions	2017	David G. Harris
+	Explicit Dimension Reduction and Its Applications	2011	Zohar Karnin Yuval Rabani Amir Shpilka
+	Simple Analysis of Sparse, Sign-Consistent JL	2017	Meena Jagadeesan

Works Cited by This (13)

Action	Title	Year	Authors
+	New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property	2010	Felix Krahmer Rachel Ward
+	Derandomized dimensionality reduction with applications	2002	Lars Engebretsen Piotr Indyk Ryan O’Donnell
+ PDF Chat	A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables	1971	D. L. Hanson F. T. Wright
+	The Space Complexity of Approximating the Frequency Moments	1999	Noga Alon Yossi Matias Márió Szegedy
+	An elementary proof of a theorem of Johnson and Lindenstrauss	2002	Sanjoy Dasgupta Anupam Gupta
+	Problems and results in extremal combinatorics—I	2003	Noga Alon
+ PDF Chat	Dense Fast Random Projections and Lean Walsh Transforms	2008	Edo Liberty Nir Ailon Amit Singer
+	Explicit Dimension Reduction and Its Applications.	2009	Zohar Karnin Yuval Rabani Amir Shpilka
+	Johnson-Lindenstrauss lemma for circulant matrices	2010	Aicke Hinrichs Jan Vybíral
+	A variant of the Johnson–Lindenstrauss lemma for circulant matrices	2010	Jan Vybíral