Alexandr Andoni

ORCID

Publication Activity (10 Years)

Years Active: 2003-2023
Publications (10 Years): 60

Top Venues

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan
Differentially Private Approximate Near Neighbor Counting in High Dimensions. NeurIPS (2023)
Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser
Communication Complexity of Inner Product in Symmetric Normed Spaces. ITCS (2023)
AmirMohsen Ahanchi, Alexandr Andoni, MohammadTaghi Hajiaghayi, Marina Knittel, Peilin Zhong
Massively Parallel Tree Embeddings for High Dimensional Spaces. SPAA (2023)
Alexandr Andoni, Hengjie Zhang
Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. FOCS (2023)
Alexandr Andoni, Hengjie Zhang
Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications. CoRR (2023)
Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal
Data Structures for Density Estimation. CoRR (2023)
Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal
Data Structures for Density Estimation. ICML (2023)
Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser
Communication Complexity of Inner Product in Symmetric Normed Spaces. CoRR (2022)
Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein
Estimating the Longest Increasing Subsequence in Nearly Optimal Time. FOCS (2022)
Alexandr Andoni, Daniel Beaglehole
Learning to Hash Robustly, Guaranteed. ICML (2022)
Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein
Estimating the Longest Increasing Subsequence in Nearly Optimal Time. CoRR (2021)
Alexandr Andoni, David Cheikhi
From Average Embeddings To Nearest Neighbor Search. CoRR (2021)
Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate Nearest Neighbors Beyond Space Partitions. SODA (2021)
Alexandr Andoni, Keren Censor-Hillel, Jing Chen, Debmalya Panigrahi
Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016). SIAM J. Comput. 50 (3) (2021)
Alexandr Andoni, Daniel Beaglehole
Learning to Hash Robustly, with Guarantees. CoRR (2021)
Alexandr Andoni, Negev Shekel Nosatzki
Edit Distance in Near-Linear Time: it's a Constant Factor. CoRR (2020)
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
Streaming Complexity of SVMs. CoRR (2020)
Alexandr Andoni, Negev Shekel Nosatzki
Edit Distance in Near-Linear Time: it's a Constant Factor. FOCS (2020)
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
Streaming Complexity of SVMs. APPROX-RANDOM (2020)
Alexandr Andoni, Clifford Stein, Peilin Zhong
Parallel approximate undirected shortest paths via low hop emulators. STOC (2020)
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
Two Party Distribution Testing: Communication and Security. ICALP (2019)
Alexandr Andoni, Clifford Stein, Peilin Zhong
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. CoRR (2019)
Alexandr Andoni, Clifford Stein, Peilin Zhong
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. ICALP (2019)
Alexandr Andoni, Clifford Stein, Peilin Zhong
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. CoRR (2019)
Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
On Solving Linear Systems in Sublinear Time. ITCS (2019)
Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, Kiran Vodrahalli
Attribute-efficient learning of monomials over highly-correlated variables. ALT (2019)
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
Two Party Distribution Testing: Communication and Security. CoRR (2018)
Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, Peilin Zhong
Parallel Graph Connectivity in Log Diameter Rounds. CoRR (2018)
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong
Subspace Embedding and Linear Regression with Orlicz Norm. ICML (2018)
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
Two Party Distribution Testing: Communication and Security. IACR Cryptol. ePrint Arch. 2018 (2018)
Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price
Batch Sparse Recovery, or How to Leverage the Average Sparsity. CoRR (2018)
Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. 47 (3) (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Data-dependent hashing via nonlinear spectral gaps. STOC (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS (2018)
Alexandr Andoni, Piotr Indyk, Ilya P. Razenshteyn
Approximate Nearest Neighbor Search in High Dimensions. CoRR (2018)
Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
On Solving Linear Systems in Sublinear Time. CoRR (2018)
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong
Subspace Embedding and Linear Regression with Orlicz Norm. CoRR (2018)
Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong
Parallel Graph Connectivity in Log Diameter Rounds. FOCS (2018)
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. SODA (2017)
Alexandr Andoni, Daniel J. Hsu, Kevin Shi, Xiaorui Sun
Correspondence retrieval. COLT (2017)
Alexandr Andoni
High frequency moments via max-stability. ICASSP (2017)
Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki
LSH Forest: Practical Algorithms Made Theoretical. SODA (2017)
Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk
Editorial. ACM Trans. Algorithms 13 (2) (2017)
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate near neighbors for general symmetric norms. STOC (2017)
Alexandr Andoni, Javad Ghaderi, Daniel J. Hsu, Dan Rubenstein, Omri Weinstein
Coding with asymmetric prior knowledge. CoRR (2017)
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
On Sketching Quadratic Forms. ITCS (2016)
Alexandr Andoni, Assaf Naor, Ofer Neiman
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. ICALP (2016)
Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate Near Neighbors for General Symmetric Norms. CoRR (2016)
Alexandr Andoni, Ilya P. Razenshteyn
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. SoCG (2016)
Mihai Budiu, Rebecca Isaacs, Derek Murray, Gordon D. Plotkin, Paul Barham, Samer Al-Kiswany, Yazan Boshmaf, Qingzhou Luo, Alexandr Andoni
Interacting with Large Distributed Datasets Using Sketch. EGPGV@EuroVis (2016)
Alexandr Andoni, Huy L. Nguyên
Width of Points in the Streaming Model. ACM Trans. Algorithms 12 (1) (2016)
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. CoRR (2016)
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. CoRR (2016)
Alexandr Andoni, Ilya P. Razenshteyn
Optimal Data-Dependent Hashing for Approximate Near Neighbors. STOC (2015)
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt
Practical and Optimal LSH for Angular Distance. NIPS (2015)
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
On Sketching Quadratic Forms. CoRR (2015)
Alexandr Andoni, Ilya P. Razenshteyn
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. CoRR (2015)
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt
Practical and Optimal LSH for Angular Distance. CoRR (2015)
Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
Sketching and Embedding are Equivalent for Norms. STOC (2015)
Alexandr Andoni, Ilya P. Razenshteyn
Optimal Data-Dependent Hashing for Approximate Near Neighbors. CoRR (2015)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel Algorithms for Geometric Graph Problems. CoRR (2014)
Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
The Sketching Complexity of Graph Cuts. CoRR (2014)
Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
Spectral Approaches to Nearest Neighbor Search. FOCS (2014)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel algorithms for geometric graph problems. STOC (2014)
Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
)-Approximate Flow Sparsifiers. SODA (2014)
Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
Spectral Approaches to Nearest Neighbor Search. CoRR (2014)
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang
Learning Polynomials with Neural Networks. ICML (2014)
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn
Beyond Locality-Sensitive Hashing. SODA (2014)
Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
Sketching and Embedding are Equivalent for Norms. CoRR (2014)
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang
Learning Sparse Polynomial Functions. SODA (2014)
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn
Beyond Locality-Sensitive Hashing. CoRR (2013)
Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu
Tight Lower Bound for Linear Sketches of Moments. ICALP (1) (2013)
Alexandr Andoni, Rina Panigrahy
A Differential Equations Approach to Optimizing Regret Trade-offs CoRR (2013)
Alexandr Andoni, Atri Rudra
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword. Theory Comput. 9 (2013)
Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat
Homomorphic fingerprints under misalignments: sketching edit and shift distances. STOC (2013)
Alexandr Andoni, Huy L. Nguyen
Eigenvalues of a matrix in the streaming model. SODA (2013)
Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
Towards (1+ε)-Approximate Flow Sparsifiers. CoRR (2013)
Alexandr Andoni, Huy L. Nguyen, Yury Polyanskiy, Yihong Wu
Tight Lower Bound for Linear Sketches of Moments. CoRR (2013)
Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh
Shift Finding in Sub-Linear Time. SODA (2013)
Alexandr Andoni, Huy L. Nguyen
Width of points in the streaming model. SODA (2012)
Alexandr Andoni, Krzysztof Onak
Approximating Edit Distance in Near-Linear Time. SIAM J. Comput. 41 (6) (2012)
Alexandr Andoni, Robert Krauthgamer
The smoothed complexity of edit distance. ACM Trans. Algorithms 8 (4) (2012)
Alexandr Andoni, Krzysztof Onak
Approximating Edit Distance in Near-Linear Time CoRR (2011)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Streaming Algorithms via Precision Sampling. FOCS (2011)
Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen
Near Linear Lower Bound for Dimension Reduction in L1. FOCS (2011)
Alexandr Andoni
Nearest Neighbor Search in High-Dimensional Spaces. MFCS (2011)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity CoRR (2010)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Streaming Algorithms from Precision Sampling CoRR (2010)
Alexandr Andoni, T. S. Jayram, Mihai Patrascu
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. SODA (2010)
Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch
Global Alignment of Molecular Sequences via Ancestral State Reconstruction. ICS (2010)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS (2010)
Alexandr Andoni, Robert Krauthgamer
The Computational Hardness of Estimating Edit Distance. SIAM J. Comput. 39 (6) (2010)
Alexandr Andoni, Huy L. Nguyen
Near-Optimal Sublinear Time Algorithms for Ulam Distance. SODA (2010)
Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen
Approximate line nearest neighbor in high dimensions. SODA (2009)
Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch
Global Alignment of Molecular Sequences via Ancestral State Reconstruction CoRR (2009)
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff
Efficient Sketches for Earth-Mover Distance, with Applications. FOCS (2009)
Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
External Sampling. ICALP (1) (2009)
Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
non-embeddability barrier: algorithms for product metrics. SODA (2009)
Alexandr Andoni, Krzysztof Onak
Approximating edit distance in near-linear time. STOC (2009)
Alexandr Andoni, Dorian Croitoru, Mihai Patrascu
Hardness of Nearest Neighbor under L-infinity. FOCS (2008)

Alexandr Andoni.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Alexandr Andoni