Alexandr Andoni

126 papers A* 53A 4B 3Misc 1Journal 53Unranked 8

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search. CoRR Alexandr Andoni, Themistoklis Haris, Esty Kelman, Krzysztof Onak
2025	A*	`conf`	A Framework for Building Data Structures from Communication Protocols. STOC Alexandr Andoni, Shunhua Jiang, Omri Weinstein
2025	J	`jnl`	A Framework for Building Data Structures from Communication Protocols. CoRR Alexandr Andoni, Shunhua Jiang, Omri Weinstein
2025	A*	`conf`	Embeddings into Similarity Measures for Nearest Neighbor Search. FOCS Alexandr Andoni, Negev Shekel Nosatzki
2025	J	`jnl`	Fast attention mechanisms: a tale of parallelism. CoRR Jingwen Liu, Hantao Yu, Clayton Sanford, Alexandr Andoni, Daniel Hsu
2025	—	`conf`	Faster Algorithms for Average-Case Orthogonal Vectors and Closes Pair Problems. SOSA Josh Alman, Alexandr Andoni, Hengjie Zhang
2024	J	`jnl`	Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems. CoRR Josh Alman, Alexandr Andoni, Hengjie Zhang
2024	A*	`conf`	Statistical-Computational Trade-offs for Density Estimation. NeurIPS Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Haike Xu
2024	J	`jnl`	Statistical-Computational Trade-offs for Density Estimation. CoRR Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Haike Xu
2023	A	`conf`	Communication Complexity of Inner Product in Symmetric Normed Spaces. ITCS Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser
2023	A*	`conf`	Data Structures for Density Estimation. ICML Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal
2023	J	`jnl`	Data Structures for Density Estimation. CoRR Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal
2023	A*	`conf`	Differentially Private Approximate Near Neighbor Counting in High Dimensions. NeurIPS Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan
2023	B	`conf`	Massively Parallel Tree Embeddings for High Dimensional Spaces. SPAA AmirMohsen Ahanchi, Alexandr Andoni, MohammadTaghi Hajiaghayi, Marina Knittel, Peilin Zhong
2023	J	`jnl`	Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications. CoRR Alexandr Andoni, Hengjie Zhang
2023	A*	`conf`	Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. FOCS Alexandr Andoni, Hengjie Zhang
2022	J	`jnl`	Communication Complexity of Inner Product in Symmetric Normed Spaces. CoRR Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser
2022	A*	`conf`	Estimating the Longest Increasing Subsequence in Nearly Optimal Time. FOCS Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein
2022	A*	`conf`	Learning to Hash Robustly, Guaranteed. ICML Alexandr Andoni, Daniel Beaglehole
2021	A*	`conf`	Approximate Nearest Neighbors Beyond Space Partitions. SODA Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2021	J	`jnl`	Estimating the Longest Increasing Subsequence in Nearly Optimal Time. CoRR Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein
2021	J	`jnl`	From Average Embeddings To Nearest Neighbor Search. CoRR Alexandr Andoni, David Cheikhi
2021	J	`jnl`	Learning to Hash Robustly, with Guarantees. CoRR Alexandr Andoni, Daniel Beaglehole
2021	J	`jnl`	Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016). SIAM J. Comput. Alexandr Andoni, Keren Censor-Hillel, Jing Chen, Debmalya Panigrahi
2020	A*	`conf`	Edit Distance in Near-Linear Time: it's a Constant Factor. FOCS Alexandr Andoni, Negev Shekel Nosatzki
2020	J	`jnl`	Edit Distance in Near-Linear Time: it's a Constant Factor. CoRR Alexandr Andoni, Negev Shekel Nosatzki
2020	A*	`conf`	Parallel approximate undirected shortest paths via low hop emulators. STOC Alexandr Andoni, Clifford Stein, Peilin Zhong
2020	—	`conf`	Streaming Complexity of SVMs. APPROX-RANDOM Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
2020	J	`jnl`	Streaming Complexity of SVMs. CoRR Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
2019	B	`conf`	Attribute-efficient learning of monomials over highly-correlated variables. ALT Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, Kiran Vodrahalli
2019	A*	`conf`	Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. ICALP Alexandr Andoni, Clifford Stein, Peilin Zhong
2019	J	`jnl`	Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. CoRR Alexandr Andoni, Clifford Stein, Peilin Zhong
2019	A	`conf`	On Solving Linear Systems in Sublinear Time. ITCS Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
2019	J	`jnl`	Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. CoRR Alexandr Andoni, Clifford Stein, Peilin Zhong
2019	A*	`conf`	Two Party Distribution Testing: Communication and Security. ICALP Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
2018	J	`jnl`	Approximate Nearest Neighbor Search in High Dimensions. CoRR Alexandr Andoni, Piotr Indyk, Ilya P. Razenshteyn
2018	J	`jnl`	Batch Sparse Recovery, or How to Leverage the Average Sparsity. CoRR Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price
2018	A*	`conf`	Data-dependent hashing via nonlinear spectral gaps. STOC Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2018	A*	`conf`	Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2018	J	`jnl`	On Solving Linear Systems in Sublinear Time. CoRR Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
2018	A*	`conf`	Parallel Graph Connectivity in Log Diameter Rounds. FOCS Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong
2018	J	`jnl`	Parallel Graph Connectivity in Log Diameter Rounds. CoRR Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, Peilin Zhong
2018	J	`jnl`	Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
2018	A*	`conf`	Subspace Embedding and Linear Regression with Orlicz Norm. ICML Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong
2018	J	`jnl`	Subspace Embedding and Linear Regression with Orlicz Norm. CoRR Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong
2018	J	`jnl`	Two Party Distribution Testing: Communication and Security. CoRR Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
2018	J	`jnl`	Two Party Distribution Testing: Communication and Security. IACR Cryptol. ePrint Arch. Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
2017	A*	`conf`	Approximate near neighbors for general symmetric norms. STOC Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2017	J	`jnl`	Coding with asymmetric prior knowledge. CoRR Alexandr Andoni, Javad Ghaderi, Daniel J. Hsu, Dan Rubenstein, Omri Weinstein
2017	A*	`conf`	Correspondence retrieval. COLT Alexandr Andoni, Daniel J. Hsu, Kevin Shi, Xiaorui Sun
2017	J	`jnl`	Editorial. ACM Trans. Algorithms Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk
2017	Misc	`conf`	High frequency moments via max-stability. ICASSP Alexandr Andoni
2017	A*	`conf`	LSH Forest: Practical Algorithms Made Theoretical. SODA Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki
2017	A*	`conf`	Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. SODA Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
2016	J	`jnl`	Approximate Near Neighbors for General Symmetric Norms. CoRR Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2016	—	`ch.`	High-Dimensional Computational Geometry. Handbook of Big Data Alexandr Andoni
2016	A*	`conf`	Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. ICALP Alexandr Andoni, Assaf Naor, Ofer Neiman
2016	—	`conf`	Interacting with Large Distributed Datasets Using Sketch. EGPGV@EuroVis Mihai Budiu, Rebecca Isaacs, Derek Murray, Gordon D. Plotkin, Paul Barham, Samer Al-Kiswany, Yazan Boshmaf, Qingzhou Luo, Alexandr Andoni
2016	J	`jnl`	Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. CoRR Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
2016	A	`conf`	On Sketching Quadratic Forms. ITCS Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
2016	J	`jnl`	Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. CoRR Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
2016	A*	`conf`	Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. SoCG Alexandr Andoni, Ilya P. Razenshteyn
2016	J	`jnl`	Width of Points in the Streaming Model. ACM Trans. Algorithms Alexandr Andoni, Huy L. Nguyên
2015	J	`jnl`	On Sketching Quadratic Forms. CoRR Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang
2015	A*	`conf`	Optimal Data-Dependent Hashing for Approximate Near Neighbors. STOC Alexandr Andoni, Ilya P. Razenshteyn
2015	J	`jnl`	Optimal Data-Dependent Hashing for Approximate Near Neighbors. CoRR Alexandr Andoni, Ilya P. Razenshteyn
2015	—	`conf`	Practical and Optimal LSH for Angular Distance. NIPS Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt
2015	J	`jnl`	Practical and Optimal LSH for Angular Distance. CoRR Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt
2015	A*	`conf`	Sketching and Embedding are Equivalent for Norms. STOC Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
2015	J	`jnl`	Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. CoRR Alexandr Andoni, Ilya P. Razenshteyn
2014	A*	`conf`	Beyond Locality-Sensitive Hashing. SODA Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn
2014	A*	`conf`	Learning Polynomials with Neural Networks. ICML Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang
2014	A*	`conf`	Learning Sparse Polynomial Functions. SODA Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang
2014	J	`jnl`	Parallel Algorithms for Geometric Graph Problems. CoRR Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
2014	A*	`conf`	Parallel algorithms for geometric graph problems. STOC Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
2014	J	`jnl`	Sketching and Embedding are Equivalent for Norms. CoRR Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
2014	A*	`conf`	Spectral Approaches to Nearest Neighbor Search. FOCS Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
2014	J	`jnl`	Spectral Approaches to Nearest Neighbor Search. CoRR Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
2014	J	`jnl`	The Sketching Complexity of Graph Cuts. CoRR Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
2014	A*	`conf`	Towards (1 + SODA Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
2013	J	`jnl`	A Differential Equations Approach to Optimizing Regret Trade-offs CoRR Alexandr Andoni, Rina Panigrahy
2013	J	`jnl`	Beyond Locality-Sensitive Hashing. CoRR Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn
2013	A*	`conf`	Eigenvalues of a matrix in the streaming model. SODA Alexandr Andoni, Huy L. Nguyen
2013	A*	`conf`	Homomorphic fingerprints under misalignments: sketching edit and shift distances. STOC Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat
2013	A*	`conf`	Shift Finding in Sub-Linear Time. SODA Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh
2013	J	`jnl`	Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword. Theory Comput. Alexandr Andoni, Atri Rudra
2013	—	`conf`	Tight Lower Bound for Linear Sketches of Moments. ICALP (1) Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu
2013	J	`jnl`	Tight Lower Bound for Linear Sketches of Moments. CoRR Alexandr Andoni, Huy L. Nguyen, Yury Polyanskiy, Yihong Wu
2013	J	`jnl`	Towards (1+ε)-Approximate Flow Sparsifiers. CoRR Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
2012	J	`jnl`	Approximating Edit Distance in Near-Linear Time. SIAM J. Comput. Alexandr Andoni, Krzysztof Onak
2012	J	`jnl`	The smoothed complexity of edit distance. ACM Trans. Algorithms Alexandr Andoni, Robert Krauthgamer
2012	A*	`conf`	Width of points in the streaming model. SODA Alexandr Andoni, Huy L. Nguyen
2011	J	`jnl`	Approximating Edit Distance in Near-Linear Time CoRR Alexandr Andoni, Krzysztof Onak
2011	A*	`conf`	Near Linear Lower Bound for Dimension Reduction in L1. FOCS Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen
2011	B	`conf`	Nearest Neighbor Search in High-Dimensional Spaces. MFCS Alexandr Andoni
2011	A*	`conf`	Streaming Algorithms via Precision Sampling. FOCS Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	A	`conf`	Global Alignment of Molecular Sequences via Ancestral State Reconstruction. ICS Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch
2010	A*	`conf`	Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. SODA Alexandr Andoni, T. S. Jayram, Mihai Patrascu
2010	A*	`conf`	Near-Optimal Sublinear Time Algorithms for Ulam Distance. SODA Alexandr Andoni, Huy L. Nguyen
2010	J	`jnl`	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity CoRR Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	A*	`conf`	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	—	`ch.`	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Property Testing Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	J	`jnl`	Streaming Algorithms from Precision Sampling CoRR Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010	—	`ch.`	Sublinear Algorithms in the External Memory Model. Property Testing Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
2010	J	`jnl`	The Computational Hardness of Estimating Edit Distance. SIAM J. Comput. Alexandr Andoni, Robert Krauthgamer
2009	A*	`conf`	Approximate line nearest neighbor in high dimensions. SODA Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen
2009	A*	`conf`	Approximating edit distance in near-linear time. STOC Alexandr Andoni, Krzysztof Onak
2009	A*	`conf`	Efficient Sketches for Earth-Mover Distance, with Applications. FOCS Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff
2009	—	`conf`	External Sampling. ICALP (1) Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
2009	J	`jnl`	Global Alignment of Molecular Sequences via Ancestral State Reconstruction CoRR Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch
2009	—	`—`	NN search : the old, the new, and the impossible. Alexandr Andoni
2009	A*	`conf`	Overcoming the SODA Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
2008	J	`jnl`	Better Bounds for Frequency Moments in Random-Order Streams CoRR Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy
2008	—	`conf`	Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03). SIGMOD Conference Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar
2008	A*	`conf`	Earth mover distance over high-dimensional spaces. SODA Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
2008	A*	`conf`	Hardness of Nearest Neighbor under L-infinity. FOCS Alexandr Andoni, Dorian Croitoru, Mihai Patrascu
2008	J	`jnl`	Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM Alexandr Andoni, Piotr Indyk
2008	—	`conf`	The Smoothed Complexity of Edit Distance. ICALP (1) Alexandr Andoni, Robert Krauthgamer
2007	J	`jnl`	Earth Mover Distance over High-Dimensional Spaces. Electron. Colloquium Comput. Complex. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer
2007	A*	`conf`	Testing k-wise and almost k-wise independence. STOC Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie
2007	A*	`conf`	The Computational Hardness of Estimating Edit Distance [Extended Abstract]. FOCS Alexandr Andoni, Robert Krauthgamer
2006	A*	`conf`	Efficient algorithms for substring near neighbor problem. SODA Alexandr Andoni, Piotr Indyk
2006	A*	`conf`	Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. FOCS Alexandr Andoni, Piotr Indyk
2006	A*	`conf`	On the Optimality of the Dimensionality Reduction Method. FOCS Alexandr Andoni, Piotr Indyk, Mihai Patrascu
2005	A*	`conf`	Graceful service degradation (or, how to know your payment is late). EC Alexandr Andoni, Jessica Staddon
2003	A*	`conf`	Lower bounds for embedding edit distance into normed spaces. SODA Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova