Alexandr Andoni

According to our database, Alexandr Andoni authored at least 88 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Statistical-Computational Trade-offs for Density Estimation.

Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Haike Xu

CoRR, 2024

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems.

Josh Alman, Alexandr Andoni, Hengjie Zhang

CoRR, 2024

2023

Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications.

Alexandr Andoni, Hengjie Zhang

CoRR, 2023

Massively Parallel Tree Embeddings for High Dimensional Spaces.

AmirMohsen Ahanchi, Alexandr Andoni, MohammadTaghi Hajiaghayi, Marina Knittel, Peilin Zhong

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Differentially Private Approximate Near Neighbor Counting in High Dimensions.

Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan

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

Communication Complexity of Inner Product in Symmetric Normed Spaces.

Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Data Structures for Density Estimation.

Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal

Proceedings of the International Conference on Machine Learning, 2023

Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications.

Alexandr Andoni, Hengjie Zhang

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Learning to Hash Robustly, Guaranteed.

Alexandr Andoni, Daniel Beaglehole

Proceedings of the International Conference on Machine Learning, 2022

Estimating the Longest Increasing Subsequence in Nearly Optimal Time.

Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016).

Alexandr Andoni, Keren Censor-Hillel, Jing Chen, Debmalya Panigrahi

SIAM J. Comput., 2021

Learning to Hash Robustly, with Guarantees.

Alexandr Andoni, Daniel Beaglehole

CoRR, 2021

From Average Embeddings To Nearest Neighbor Search.

Alexandr Andoni, David Cheikhi

CoRR, 2021

Approximate Nearest Neighbors Beyond Space Partitions.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

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

2020

Parallel approximate undirected shortest paths via low hop emulators.

Alexandr Andoni, Clifford Stein, Peilin Zhong

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

Edit Distance in Near-Linear Time: it's a Constant Factor.

Alexandr Andoni, Negev Shekel Nosatzki

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

Streaming Complexity of SVMs.

Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff

Proceedings of the Approximation, 2020

2019

On Solving Linear Systems in Sublinear Time.

Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity.

Alexandr Andoni, Clifford Stein, Peilin Zhong

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Attribute-efficient learning of monomials over highly-correlated variables.

Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, Kiran Vodrahalli

Proceedings of the Algorithmic Learning Theory, 2019

2018

Sketching and Embedding are Equivalent for Norms.

Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn

SIAM J. Comput., 2018

Two Party Distribution Testing: Communication and Security.

Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki

IACR Cryptol. ePrint Arch., 2018

Batch Sparse Recovery, or How to Leverage the Average Sparsity.

Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price

CoRR, 2018

Approximate Nearest Neighbor Search in High Dimensions.

Alexandr Andoni, Piotr Indyk, Ilya P. Razenshteyn

CoRR, 2018

Data-dependent hashing via nonlinear spectral gaps.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

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

Subspace Embedding and Linear Regression with Orlicz Norm.

Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong

Proceedings of the 35th International Conference on Machine Learning, 2018

Parallel Graph Connectivity in Log Diameter Rounds.

Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong

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

Hölder Homeomorphisms and Approximate Nearest Neighbors.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

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

2017

Editorial.

Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk

ACM Trans. Algorithms, 2017

Coding with asymmetric prior knowledge.

Alexandr Andoni, Javad Ghaderi, Daniel J. Hsu, Dan Rubenstein, Omri Weinstein

CoRR, 2017

Approximate near neighbors for general symmetric norms.

Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

LSH Forest: Practical Algorithms Made Theoretical.

Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki

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

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors.

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

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

High frequency moments via max-stability.

Alexandr Andoni

Proceedings of the 2017 IEEE International Conference on Acoustics, 2017

Correspondence retrieval.

Alexandr Andoni, Daniel J. Hsu, Kevin Shi, Xiaorui Sun

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Width of Points in the Streaming Model.

Alexandr Andoni, Huy L. Nguyên

ACM Trans. Algorithms, 2016

Approximate Near Neighbors for General Symmetric Norms.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors.

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

On Sketching Quadratic Forms.

Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost.

Alexandr Andoni, Assaf Naor, Ofer Neiman

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Interacting with Large Distributed Datasets Using Sketch.

Mihai Budiu, Rebecca Isaacs, Derek Murray, Gordon D. Plotkin, Paul Barham, Samer Al-Kiswany, Yazan Boshmaf, Qingzhou Luo, Alexandr Andoni

Proceedings of the 16th Eurographics Symposium on Parallel Graphics and Visualization, 2016

Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing.

Alexandr Andoni, Ilya P. Razenshteyn

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

High-Dimensional Computational Geometry.

Alexandr Andoni

Proceedings of the Handbook of Big Data., 2016

2015

Optimal Data-Dependent Hashing for Approximate Near Neighbors.

Alexandr Andoni, Ilya P. Razenshteyn

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Practical and Optimal LSH for Angular Distance.

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

2014

The Sketching Complexity of Graph Cuts.

Alexandr Andoni, Robert Krauthgamer, David P. Woodruff

CoRR, 2014

Parallel algorithms for geometric graph problems.

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev

Proceedings of the Symposium on Theory of Computing, 2014

Learning Sparse Polynomial Functions.

Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Beyond Locality-Sensitive Hashing.

Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Towards (1 + <i>∊</i>)-Approximate Flow Sparsifiers.

Alexandr Andoni, Anupam Gupta, Robert Krauthgamer

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Learning Polynomials with Neural Networks.

Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang

Proceedings of the 31th International Conference on Machine Learning, 2014

Spectral Approaches to Nearest Neighbor Search.

Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword.

Alexandr Andoni, Atri Rudra

Theory Comput., 2013

A Differential Equations Approach to Optimizing Regret Trade-offs

Alexandr Andoni, Rina Panigrahy

CoRR, 2013

Towards (1+ε)-Approximate Flow Sparsifiers.

Alexandr Andoni, Anupam Gupta, Robert Krauthgamer

CoRR, 2013

Homomorphic fingerprints under misalignments: sketching edit and shift distances.

Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat

Proceedings of the Symposium on Theory of Computing Conference, 2013

Eigenvalues of a matrix in the streaming model.

Alexandr Andoni, Huy L. Nguyen

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Shift Finding in Sub-Linear Time.

Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Tight Lower Bound for Linear Sketches of Moments.

Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

The smoothed complexity of edit distance.

Alexandr Andoni, Robert Krauthgamer

ACM Trans. Algorithms, 2012

Approximating Edit Distance in Near-Linear Time.

Alexandr Andoni, Krzysztof Onak

SIAM J. Comput., 2012

2011

Nearest Neighbor Search in High-Dimensional Spaces.

Alexandr Andoni

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Streaming Algorithms via Precision Sampling.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Near Linear Lower Bound for Dimension Reduction in L1.

Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

The Computational Hardness of Estimating Edit Distance.

Alexandr Andoni, Robert Krauthgamer

SIAM J. Comput., 2010

Streaming Algorithms from Precision Sampling

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

CoRR, 2010

Near-Optimal Sublinear Time Algorithms for Ulam Distance.

Alexandr Andoni, Huy L. Nguyen

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities.

Alexandr Andoni, T. S. Jayram, Mihai Patrascu

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear Algorithms in the External Memory Model.

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Property Testing - Current Research and Surveys, 2010

Global Alignment of Molecular Sequences via Ancestral State Reconstruction.

Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch

Proceedings of the Innovations in Computer Science, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

NN search : the old, the new, and the impossible.

Alexandr Andoni

PhD thesis, 2009

Approximate line nearest neighbor in high dimensions.

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Overcoming the <i>l</i>₁ non-embeddability barrier: algorithms for product metrics.

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

External Sampling.

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Efficient Sketches for Earth-Mover Distance, with Applications.

Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Better Bounds for Frequency Moments in Random-Order Streams

Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy

CoRR, 2008

Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.

Alexandr Andoni, Piotr Indyk

Commun. ACM, 2008

Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03).

Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Hardness of Nearest Neighbor under L-infinity.

Alexandr Andoni, Dorian Croitoru, Mihai Patrascu

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Earth Mover Distance over High-Dimensional Spaces.

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

Electron. Colloquium Comput. Complex., 2007

Testing k-wise and almost k-wise independence.

Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

The Computational Hardness of Estimating Edit Distance [Extended Abstract].

Alexandr Andoni, Robert Krauthgamer

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Efficient algorithms for substring near neighbor problem.

Alexandr Andoni, Piotr Indyk

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

On the Optimality of the Dimensionality Reduction Method.

Alexandr Andoni, Piotr Indyk, Mihai Patrascu

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Graceful service degradation (or, how to know your payment is late).

Alexandr Andoni, Jessica Staddon

Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005

2003

Lower bounds for embedding edit distance into normed spaces.

Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003