Sepideh Mahabadi

Mohammad Roghani

Jakub Tarnawski

CoRR, June, 2025

Graph-Based Algorithms for Diverse Similarity Search.

[BibT_eX]

[DOI]

Piyush Anand

Piotr Indyk

Ravishankar Krishnaswamy

CoRR, February, 2025

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover.

[BibT_eX]

[DOI]

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time.

[BibT_eX]

[DOI]

Mohammad Roghani

Jakub Tarnawski

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Guessing Efficiently for Constrained Subspace Approximation.

[BibT_eX]

[DOI]

Aditya Bhaskara

Madhusudhan Reddy Pittu

David P. Woodruff

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Streaming Algorithms for Network Design.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2025

2024

Efficiently Computing Similarities to Private Datasets.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Streaming Algorithms for Connectivity Augmentation.

[BibT_eX]

[DOI]

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

2023

Core-sets for Fair and Diverse Data Summarization.

[BibT_eX]

[DOI]

Stojan Trajanovski

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

Composable Coresets for Determinant Maximization: Greedy is Almost Optimal.

[BibT_eX]

[DOI]

Siddharth Gollapudi

Varun Sivashankar

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

Tight Bounds for Volumetric Spanners and Applications.

[BibT_eX]

[DOI]

Aditya Bhaskara

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

Differentially Private Approximate Near Neighbor Counting in High Dimensions.

[BibT_eX]

[DOI]

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

Approximation Algorithms for Fair Range Clustering.

[BibT_eX]

[DOI]

Sèdjro Salomon Hotegni

Proceedings of the International Conference on Machine Learning, 2023

Improved Diversity Maximization Algorithms for Matching and Pseudoforest.

[BibT_eX]

[DOI]

Shyam Narayanan

Proceedings of the Approximation, 2023

2022

Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All?

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2022

Composable Coresets for Constrained Determinant Maximization and Beyond.

[BibT_eX]

[DOI]

Thuy-Duong Vuong

CoRR, 2022

Sampling near neighbors in search for fairness.

[BibT_eX]

[DOI]

Commun. ACM, 2022

Adaptive Sketches for Robust Regression with Importance Sampling.

[BibT_eX]

[DOI]

David P. Woodruff

Samson Zhou

Proceedings of the Approximation, 2022

2021

Fair near neighbor search via sampling.

[BibT_eX]

[DOI]

SIGMOD Rec., 2021

Two-Sided Kirszbraun Theorem.

[BibT_eX]

[DOI]

Arturs Backurs

Konstantin Makarychev

Yury Makarychev

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Non-adaptive adaptive sampling on turnstile streams.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners.

[BibT_eX]

[DOI]

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

Individual Fairness for k-Clustering.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Towards Better Approximation of Graph Crossing Number.

[BibT_eX]

[DOI]

Julia Chuzhoy

Zihan Tan

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

Streaming Complexity of SVMs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Near Neighbor: Who is the Fairest of Them All?

[BibT_eX]

[DOI]

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

Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

2018

Nonlinear dimension reduction via outer Bi-Lipschitz extensions.

[BibT_eX]

[DOI]

Konstantin Makarychev

Yury Makarychev

Ilya P. Razenshteyn

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Set Cover in Sub-linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Approximate Sparse Linear Regression.

[BibT_eX]

[DOI]

Piotr Indyk

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Sublinear algorithms for massive data problems.

[BibT_eX]

[DOI]

PhD thesis, 2017

LSH on the Hypercube Revisited.

[BibT_eX]

[DOI]

CoRR, 2017

Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Fractional Set Cover in the Streaming Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Towards Tight Bounds for the Streaming Set Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Simultaneous Nearest Neighbor Search.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Towards Tight Bounds for the Streaming Set Cover Problem.

[BibT_eX]

[DOI]

Piotr Indyk

CoRR, 2015

Approximate Nearest Line Search in High Dimensions.

[BibT_eX]

[DOI]