Rajesh Jayaram

Samson Zhou

Proc. ACM Manag. Data, 2024

Efficient Centroid-Linkage Clustering.

[BibT_eX]

[DOI]

CoRR, 2024

MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings.

[BibT_eX]

[DOI]

CoRR, 2024

Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search.

[BibT_eX]

[DOI]

CoRR, 2024

Data-Dependent LSH for the Earth Mover's Distance.

[BibT_eX]

[DOI]

Erik Waingarten

Tian Zhang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Fully Dynamic Consistent k-Center Clustering.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

HyperAttention: Long-context Attention in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Dynamic PageRank: Algorithms and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

It's Hard to HAC Average Linkage!

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Metric Clustering and MST with Strong and Weak Distance Oracles.

[BibT_eX]

[DOI]

Prathamesh Dharangutte

Chen Wang

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Towards Optimal Moment Estimation in Streaming and Distributed Models.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, July, 2023

Technical Perspective: Optimal Algorithms for Multiway Search on Partial Orders.

[BibT_eX]

[DOI]

SIGMOD Rec., 2023

A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies.

[BibT_eX]

[DOI]

CoRR, 2023

Fully Dynamic Consistent k-Center Clustering.

[BibT_eX]

[DOI]

CoRR, 2023

Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries.

[BibT_eX]

[DOI]

Hossein Esfandiari

Hendrik Fichtenberger

CoRR, 2023

Streaming Euclidean MST to a Constant Factor.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries.

[BibT_eX]

[DOI]

Hossein Esfandiari

Hendrik Fichtenberger

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Near-Linear Time Algorithm for the Chamfer Distance.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

Counting the Answers to a Query.

[BibT_eX]

[DOI]

SIGMOD Rec., 2022

Differentially Oblivious Relational Database Operators.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2022

Adore: Differentially Oblivious Relational Database Operators.

[BibT_eX]

[DOI]

CoRR, 2022

Stars: Tera-Scale Graph Building for Clustering and Graph Learning.

[BibT_eX]

[DOI]

CoRR, 2022

New streaming algorithms for high dimensional EMD and MST.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Truly Perfect Samplers for Data Streams and Sliding Windows.

[BibT_eX]

[DOI]

Samson Zhou

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Stars: Tera-Scale Graph Building for Clustering and Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Sketching and Sampling Algorithms for High-Dimensional Data.

[BibT_eX]

[DOI]

PhD thesis, 2021

A Framework for Adversarially Robust Streaming Algorithms.

[BibT_eX]

[DOI]

SIGMOD Rec., 2021

Perfect Lp Sampling in a Data Stream.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes.

[BibT_eX]

[DOI]

J. ACM, 2021

Optimal Fully Dynamic k-Centers Clustering.

[BibT_eX]

[DOI]

Hossein Esfandiari

Vahab S. Mirrokni

CoRR, 2021

An Optimal Algorithm for Triangle Counting.

[BibT_eX]

[DOI]

John Kallaugher

CoRR, 2021

When is approximate counting for conjunctive queries tractable?

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper).

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

In-Database Regression in Input Sparsity Time.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Learning and testing junta distributions with sub cube conditioning.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

An Optimal Algorithm for Triangle Counting in the Stream.

[BibT_eX]

[DOI]

John Kallaugher

Proceedings of the Approximation, 2021

2020

Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation.

[BibT_eX]

[DOI]

SIGMOD Rec., 2020

An FPRAS and Polynomial-Time Uniform Sampler for Tree Automata.

[BibT_eX]

[DOI]

CoRR, 2020

Learning and Testing Junta Distributions with Subcube Conditioning.

[BibT_eX]

[DOI]

CoRR, 2020

Span Recovery for Deep Neural Networks with Applications to Input Obfuscation.

[BibT_eX]

[DOI]

Qiuyi Zhang

Proceedings of the 8th International Conference on Learning Representations, 2020

Testing Positive Semi-Definiteness via Random Submatrices.

[BibT_eX]

[DOI]

Ainesh Bakshi

Nadiia Chepurko

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Weighted Reservoir Sampling from Distributed Streams.

[BibT_eX]

[DOI]

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Learning Two Layer Rectified Neural Networks in Polynomial Time.

[BibT_eX]

[DOI]

Ainesh Bakshi

Proceedings of the Conference on Learning Theory, 2019

2018

Data Streams with Bounded Deletions.

[BibT_eX]

[DOI]

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Perfect Lp Sampling in a Data Stream.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!.

[BibT_eX]

[DOI]