Rajesh Jayaram

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
It's hard to HAC average linkage!	2026-01-14	Paper
Dynamic pagerank: algorithms and lower bounds	2026-01-14	Paper
Perfect L_p sampling in a data stream	2025-08-12	Paper
Testing positive semi-definiteness via random submatrices	2025-08-12	Paper
Massively parallel algorithms for high-dimensional Euclidean minimum spanning tree	2024-11-28	Paper
Fully dynamic consistent k-center clustering	2024-11-28	Paper
Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries	2024-05-14	Paper
Streaming Euclidean MST to a constant factor	2024-05-08	Paper
New streaming algorithms for high dimensional EMD and MST Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
An Optimal Algorithm for Triangle Counting in the Stream (available as arXiv preprint)	2023-11-20	Paper
A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper) Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
When is approximate counting for conjunctive queries tractable? Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
Towards Optimal Moment Estimation in Streaming and Distributed Models ACM Transactions on Algorithms	2023-10-23	Paper
Towards Optimal Moment Estimation in Streaming and Distributed Models (available as arXiv preprint)	2023-02-03	Paper
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes Journal of the ACM	2022-12-08	Paper
A Framework for Adversarially Robust Streaming Algorithms Journal of the ACM	2022-03-31	Paper
Perfect \(L_p\) sampling in a data stream SIAM Journal on Computing	2021-04-14	Paper
Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!	2020-05-27	Paper
Learning and Testing Junta Distributions with Subcube Conditioning	2020-04-26	Paper

Research outcomes over time

This page was built for person: Rajesh Jayaram