Rajesh Jayaram

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	Massively Parallel Minimum Spanning Tree in General Metric Spaces	2025	Amir Azarmehr Soheil Behnezhad Rajesh Jayaram Jakub Łącki Vahab Mirrokni Peilin Zhong
+ PDF Chat	Massively Parallel Minimum Spanning Tree in General Metric Spaces	2024	Amir Azarmehr Soheil Behnezhad Rajesh Jayaram Jakub Łącki Vahab Mirrokni Peilin Zhong
+	Data-Dependent LSH for the Earth Mover’s Distance	2024	Rajesh Jayaram Erik Waingarten Tian Zhang
+ PDF Chat	Streaming Algorithms with Few State Changes	2024	Rajesh Jayaram David P. Woodruff Samson Zhou
+ PDF Chat	Efficient Centroid-Linkage Clustering	2024	MohammadHossein Bateni Laxman Dhulipala Willem Fletcher Kishen N Gowda D Ellis Hershkowitz Rajesh Jayaram Jakub Łącki
+ PDF Chat	MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings	2024	Laxman Dhulipala Majid Hadian Rajesh Jayaram J. S. H. Lee Vahab Mirrokni
+ PDF Chat	Streaming Algorithms with Few State Changes	2024	Rajesh Jayaram David P. Woodruff Samson Zhou
+ PDF Chat	Dynamic PageRank: Algorithms and Lower Bounds	2024	Rajesh Jayaram Jakub Łącki Slobodan Mitrović Krzysztof Onak Piotr Sankowski
+ PDF Chat	It's Hard to HAC with Average Linkage!	2024	MohammadHossein Bateni Laxman Dhulipala Kishen N Gowda D Ellis Hershkowitz Rajesh Jayaram Jakub Łącki
+ PDF Chat	Data-Dependent LSH for the Earth Mover's Distance	2024	Rajesh Jayaram Erik Waingarten Tian Zhang
+ PDF Chat	Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search	2024	Lars Gottesbüren Laxman Dhulipala Rajesh Jayaram Jakub Łącki
+ PDF Chat	Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree	2024	Rajesh Jayaram Vahab Mirrokni Shyam Narayanan Peilin Zhong
+	Streaming Euclidean MST to a Constant Factor	2023	Xi Chen Vincent Cohen-Addad Rajesh Jayaram Amit Levi Erik Waingarten
+	Towards Optimal Moment Estimation in Streaming and Distributed Models	2023	Rajesh Jayaram David P. Woodruff
+ PDF Chat	Optimal Fully Dynamic <i>k</i>-Center Clustering for Adaptive and Oblivious Adversaries	2023	MohammadHossein Bateni Hossein Esfandiari Hendrik Fichtenberger Monika Henzinger Rajesh Jayaram Vahab Mirrokni Andreas Wiese
+	A Near-Linear Time Algorithm for the Chamfer Distance	2023	Ainesh Bakshi Piotr Indyk Rajesh Jayaram Sandeep Silwal Erik Waingarten
+	Fully Dynamic Consistent $k$-Center Clustering	2023	Jakub Łącki Bernhard Haeupler Christoph Grunau Václav Rozhoň Rajesh Jayaram
+	Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree	2023	Rajesh Jayaram Vahab Mirrokni Shyam Narayanan Peilin Zhong
+	HyperAttention: Long-context Attention in Near-Linear Time	2023	In‐Su Han Rajesh Jayaram Amin Karbasi Vahab Mirrokni David P. Woodruff Amir Zandieh
+	Metric Clustering and MST with Strong and Weak Distance Oracles	2023	MohammadHossein Bateni Prathamesh Dharangutte Rajesh Jayaram Chen Wang
+	A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies	2023	Ainesh Bakshi Vincent Cohen-Addad Samuel B. Hopkins Rajesh Jayaram Silvio Lattanzi
+	Counting the Answers to a Query	2022	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	Rajesh Jayaram David P. Woodruff Samson Zhou
+	New streaming algorithms for high dimensional EMD and MST	2022	Xi Chen Rajesh Jayaram Amit Levi Erik Waingarten
+ PDF Chat	A Framework for Adversarially Robust Streaming Algorithms	2022	Omri Ben‐Eliezer Rajesh Jayaram David P. Woodruff Eylon Yogev
+	Stars: Tera-Scale Graph Building for Clustering and Graph Learning	2022	CJ Carey Jonathan Halcrow Rajesh Jayaram Vahab Mirrokni Warren Schudy Peilin Zhong
+	Adore: Differentially Oblivious Relational Database Operators	2022	Lianke Qin Rajesh Jayaram Elaine Shi Zhao Song Danyang Zhuo Shumo Chu
+	Streaming Euclidean MST to a Constant Factor	2022	Vincent Cohen-Addad Xi Chen Rajesh Jayaram Amit Levi Erik Waingarten
+ PDF Chat	Optimal Fully Dynamic $k$-Centers Clustering	2021	MohammadHossein Bateni Hossein Esfandiari Rajesh Jayaram Vahab Mirrokni
+	A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper)	2021	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+ PDF Chat	When is approximate counting for conjunctive queries tractable?	2021	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+ PDF Chat	A Framework for Adversarially Robust Streaming Algorithms	2021	Omri Ben‐Eliezer Rajesh Jayaram David P. Woodruff Eylon Yogev
+	An Optimal Algorithm for Triangle Counting.	2021	Rajesh Jayaram John Kallaugher
+	An Optimal Algorithm for Triangle Counting in the Stream.	2021	Rajesh Jayaram John Kallaugher
+ PDF Chat	Perfect $L_p$ Sampling in a Data Stream	2021	Rajesh Jayaram David P. Woodruff
+	In-Database Regression in Input Sparsity Time	2021	Rajesh Jayaram Alireza Samadian David P. Woodruff Peng Ye
+	New Streaming Algorithms for High Dimensional EMD and MST	2021	Xi Chen Rajesh Jayaram Amit Levi Erik Waingarten
+	An Optimal Algorithm for Triangle Counting in the Stream	2021	Rajesh Jayaram John Kallaugher
+	Optimal Fully Dynamic $k$-Centers Clustering	2021	MohammadHossein Bateni Hossein Esfandiari Rajesh Jayaram Vahab Mirrokni
+	Truly Perfect Samplers for Data Streams and Sliding Windows	2021	Rajesh Jayaram David P. Woodruff Samson Zhou
+ PDF Chat	Testing Positive Semi-Definiteness via Random Submatrices	2020	Ainesh Bakshi Nadiia Chepurko Rajesh Jayaram
+ PDF Chat	A Framework for Adversarially Robust Streaming Algorithms	2020	Omri Ben‐Eliezer Rajesh Jayaram David P. Woodruff Eylon Yogev
+	An FPRAS and Polynomial-Time Uniform Sampler for Tree Automata.	2020	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	When is Approximate Counting for Conjunctive Queries Tractable	2020	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	Testing Positive Semi-Definiteness via Random Submatrices	2020	Ainesh Bakshi Nadiia Chepurko Rajesh Jayaram
+	Span Recovery for Deep Neural Networks with Applications to Input Obfuscation.	2020	Rajesh Jayaram David P. Woodruff Qiuyi Zhang
+	Span Recovery for Deep Neural Networks with Applications to Input Obfuscation	2020	Rajesh Jayaram David P. Woodruff Qiuyi Zhang
+	Learning and Testing Junta Distributions with Subcube Conditioning	2020	Xi Chen Rajesh Jayaram Amit Levi Erik Waingarten
+	When is Approximate Counting for Conjunctive Queries Tractable?	2020	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	Testing Positive Semi-Definiteness via Random Submatrices	2020	Ainesh Bakshi Nadiia Chepurko Rajesh Jayaram
+	Optimal Sketching for Kronecker Product Regression and Low Rank Approximation	2019	Huaian Diao Rajesh Jayaram Zhao Song Wen Sun David P. Woodruff
+	Towards Optimal Moment Estimation in Streaming and Distributed Models	2019	Rajesh Jayaram David P. Woodruff
+	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	Counting, uniform sampling, and enumeration of strings from non-deterministic finite automata	2019	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	Weighted Reservoir Sampling from Distributed Streams	2019	Rajesh Jayaram Gokarna Sharma Srikanta Tirthapura David P. Woodruff
+	Weighted Reservoir Sampling from Distributed Streams	2019	Rajesh Jayaram Gokarna Sharma Srikanta Tirthapura David P. Woodruff
+	Optimal Sketching for Kronecker Product Regression and Low Rank Approximation	2019	Huaian Diao Rajesh Jayaram Zhao Song Wen Sun David P. Woodruff
+	$\text{#NFA}$ admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	2019	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
+	Weighted Reservoir Sampling from Distributed Streams	2019	Rajesh Jayaram Gokarna Sharma Srikanta Tirthapura David P. Woodruff
+	Towards Optimal Moment Estimation in Streaming and Distributed Models	2019	Rajesh Jayaram David P. Woodruff
+	Learning Two Layer Rectified Neural Networks in Polynomial Time	2018	Ainesh Bakshi Rajesh Jayaram David P. Woodruff
+ PDF Chat	Perfect Lp Sampling in a Data Stream	2018	Rajesh Jayaram David P. Woodruff
+	Perfect $L_p$ Sampling in a Data Stream	2018	Rajesh Jayaram David P. Woodruff
+ PDF Chat	Data Streams with Bounded Deletions	2018	Rajesh Jayaram David P. Woodruff
+	Data Streams with Bounded Deletions	2018	Rajesh Jayaram David P. Woodruff
+	Learning Two Layer Rectified Neural Networks in Polynomial Time	2018	Ainesh Bakshi Rajesh Jayaram David P. Woodruff
+	Perfect $L_p$ Sampling in a Data Stream	2018	Rajesh Jayaram David P. Woodruff
+	Data Streams with Bounded Deletions	2018	Rajesh Jayaram David P. Woodruff

Common Coauthors

Coauthor	Papers Together
David P. Woodruff	28
Vahab Mirrokni	10
Cristian Riveros	9
Luis Alberto Croquevielle	9
Marcelo Arenas	9
Erik Waingarten	8
Jakub Łącki	7
Ainesh Bakshi	7
MohammadHossein Bateni	6
Peilin Zhong	5
Amit Levi	5
Samson Zhou	4
Laxman Dhulipala	4
Vincent Cohen-Addad	3
Omri Ben‐Eliezer	3
Srikanta Tirthapura	3
Hossein Esfandiari	3
Eylon Yogev	3
Gokarna Sharma	3
John Kallaugher	3
Nadiia Chepurko	3
Amir Azarmehr	2
Zhao Song	2
Xi Chen	2
Soheil Behnezhad	2
Qiuyi Zhang	2
D Ellis Hershkowitz	2
Shyam Narayanan	2
Kishen N Gowda	2
Wen Sun	2
Huaian Diao	2
Chen Wang	1
Tian Zhang	1
Zhao Song	1
Samuel B. Hopkins	1
Christoph Grunau	1
Shumo Chu	1
Peng Ye	1
Monika Henzinger	1
Danyang Zhuo	1
Amir Zandieh	1
Amin Karbasi	1
Slobodan Mitrović	1
Jonathan Halcrow	1
Silvio Lattanzi	1
Prathamesh Dharangutte	1
Piotr Sankowski	1
Sandeep Silwal	1
Hendrik Fichtenberger	1
Krzysztof Onak	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+ PDF Chat	Tight bounds for Lp samplers, finding duplicates in streams, and related problems	2011	Hossein Jowhari Mert Sağlam Gábor Tardos	12
+ PDF Chat	Random sampling with a reservoir	1985	Jeffrey Scott Vitter	8
+ PDF Chat	Perfect Lp Sampling in a Data Stream	2018	Rajesh Jayaram David P. Woodruff	8
+ PDF Chat	Optimal Random Sampling from Distributed Streams Revisited	2011	Srikanta Tirthapura David P. Woodruff	7
+	Streaming Algorithms from Precision Sampling	2010	Alexandr Andoni Robert Krauthgamer Krzysztof Onak	7
+ PDF Chat	Data Streams with Bounded Deletions	2018	Rajesh Jayaram David P. Woodruff	6
+	Order Statistics from Independent Exponential Random Variables and the Sum of the Top Order Statistics	2007	Haikady N. Nagaraja	6
+	Weighted Reservoir Sampling from Distributed Streams	2019	Rajesh Jayaram Gokarna Sharma Srikanta Tirthapura David P. Woodruff	5
+ PDF Chat	How robust are linear sketches to adaptive inputs?	2013	Moritz Hardt David P. Woodruff	5
+ PDF Chat	Sketching and Streaming Entropy via Approximation Theory	2008	Nicholas J. A. Harvey Jelani Nelson Krzysztof Onak	5
+ PDF Chat	Introduction to the non-asymptotic analysis of random matrices	2012	Roman Vershynin	5
+	The Space Complexity of Approximating the Frequency Moments	1999	Noga Alon Yossi Matias Márió Szegedy	5
+	Perfect $L_p$ Sampling in a Data Stream	2018	Rajesh Jayaram David P. Woodruff	4
+	Beating CountSketch for heavy hitters in insertion streams	2016	Vladimir Braverman Stephen R. Chestnut Nikita Ivkin David P. Woodruff	4
+ PDF Chat	A Framework for Adversarially Robust Streaming Algorithms	2020	Omri Ben‐Eliezer Rajesh Jayaram David P. Woodruff Eylon Yogev	4
+	Random generation of combinatorial structures from a uniform distribution	1986	Mark Jerrum Leslie G. Valiant Vijay V. Vazirani	4
+ PDF Chat	Heavy Hitters via Cluster-Preserving Clustering	2016	Kasper Green Larsen Jelani Nelson Huy L. Nguyễn Mikkel Thorup	4
+	Sketching as a Tool for Numerical Linear Algebra	2014	David P. Woodruff	4
+ PDF Chat	The best constants in the Khintchine inequality	1981	Uffe Haagerup	4
+ PDF Chat	Randomized algorithms for tracking distributed count, frequencies, and ranks	2012	Zengfeng Huang Ke Yi Qin Zhang	4
+ PDF Chat	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2011	Ke Yi Qin Zhang	4
+	Fast monte-carlo algorithms for finding low-rank approximations	2004	Alan Frieze Ravi Kannan Santosh Vempala	4
+ PDF Chat	Sparser Johnson-Lindenstrauss Transforms	2014	Daniel M. Kane Jelani Nelson	3
+	Monte-Carlo algorithms for enumeration and reliability problems	1983	Richard M. Karp Michael Luby	3
+	New streaming algorithms for high dimensional EMD and MST	2022	Xi Chen Rajesh Jayaram Amit Levi Erik Waingarten	3
+	Monte-Carlo approximation algorithms for enumeration problems	1989	Richard M. Karp Michael Luby Neal Madras	3
+ PDF Chat	The Adversarial Robustness of Sampling	2020	Omri Ben‐Eliezer Eylon Yogev	3
+	The Complexity of Enumeration and Reliability Problems	1979	Leslie G. Valiant	3
+ PDF Chat	Adversarially Robust Streaming Algorithms via Differential Privacy	2022	Avinatan Hassidim Haim Kaplan Yishay Mansour Yossi Matias Uri Stemmer	3
+ PDF Chat	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices	2017	Cameron Musco David P. Woodruff	3
+ PDF Chat	Adaptive estimation of a quadratic functional by model selection	2000	Béatrice Laurent Pascal Massart	3
+	Sublinear Time Low-Rank Approximation of Distance Matrices	2018	Ainesh Bakshi David P. Woodruff	3
+ PDF Chat	Parallel algorithms for geometric graph problems	2014	Alexandr Andoni Aleksandar Nikolov Krzysztof Onak Grigory Yaroslavtsev	3
+	High-Dimensional Statistics: A Non-Asymptotic Viewpoint	2019	Martin J. Wainwright	3
+ PDF Chat	On Sketching Quadratic Forms	2016	Alexandr Andoni Jiecao Chen Robert Krauthgamer Bo Qin David P. Woodruff Qin Zhang	3
+	Provable Bounds for Learning Some Deep Representations	2013	Sanjeev Arora Aditya Bhaskara Rong Ge Tengyu Ma	3
+ PDF Chat	Distributed low rank approximation of implicit functions of a matrix	2016	David P. Woodruff Peilin Zhong	3
+	A very hard log-space counting class	1993	Carme Àlvarez Birgit Jenner	3
+	Hypertree Decompositions and Tractable Queries	2002	Georg Gottlob Nicola Leone Francesco Scarcello	3
+ PDF Chat	Stream Sampling for Frequency Cap Statistics	2015	Edith Cohen	3
+	Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods	2015	Majid Janzamin Hanie Sedghi Anima Anandkumar	3
+	BPTree: an $\ell_2$ heavy hitters algorithm using constant memory	2016	Vladimir Braverman Stephen R. Chestnut Nikita Ivkin Jelani Nelson Zhengyu Wang David P. Woodruff	3
+ PDF Chat	Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams	2017	Michael Kapralov Jelani Nelson Jakub Pachocki Zhengyu Wang David P. Woodruff Mobin Yahyazadeh	3
+ PDF Chat	A simple, combinatorial algorithm for solving SDD systems in nearly-linear time	2013	Jonathan A. Kelner Lorenzo Orecchia Aaron Sidford Zeyuan Allen Zhu	2
+ PDF Chat	Learning Functions of Few Arbitrary Linear Parameters in High Dimensions	2012	Massimo Fornasier Karin Schnass Jan Vybíral	2
+	Lower bounds for sparse recovery	2010	Khanh Do Ba Piotr Indyk Eric Price David P. Woodruff	2
+ PDF Chat	Expected values of parameters associated with the minimum rank of a graph	2010	H. Tracy Hall Leslie Hogben Ryan R. Martin Bryan L. Shader	2
+	Fast algorithms for approximate semidefinite programming using the multiplicative weights update method	2005	Sanjeev Arora Elad Hazan S. Kale	2
+ PDF Chat	Weighted sampling without replacement from data streams	2015	Vladimir Braverman Rafail Ostrovsky Gregory Vorsanger	2
+ PDF Chat	Tail Bounds for All Eigenvalues of a Sum of Random Matrices	2011	Alex Gittens Joel A. Tropp	2