default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAlexandr Andoni
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[c65]Alexandr Andoni, Hengjie Zhang:
Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. FOCS 2023: 98-112- [c64]Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal:
Data Structures for Density Estimation. ICML 2023: 1-18 - [c63]Alexandr Andoni, Jaroslaw Blasiok
, Arnold Filtser:
Communication Complexity of Inner Product in Symmetric Normed Spaces. ITCS 2023: 4:1-4:22 - [c62]Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan:
Differentially Private Approximate Near Neighbor Counting in High Dimensions. NeurIPS 2023 - [c61]AmirMohsen Ahanchi, Alexandr Andoni, MohammadTaghi Hajiaghayi, Marina Knittel, Peilin Zhong:
Massively Parallel Tree Embeddings for High Dimensional Spaces. SPAA 2023: 77-88 - [i39]Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal:
Data Structures for Density Estimation. CoRR abs/2306.11312 (2023) - [i38]Alexandr Andoni, Hengjie Zhang:
Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications. CoRR abs/2310.05315 (2023) - 2022
- [c60]Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein:
Estimating the Longest Increasing Subsequence in Nearly Optimal Time. FOCS 2022: 708-719 - [c59]Alexandr Andoni, Daniel Beaglehole:
Learning to Hash Robustly, Guaranteed. ICML 2022: 599-618 - [i37]Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser:
Communication Complexity of Inner Product in Symmetric Normed Spaces. CoRR abs/2211.13473 (2022) - 2021
- [j9]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) - [c58]Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Approximate Nearest Neighbors Beyond Space Partitions. SODA 2021: 1171-1190 - [i36]Alexandr Andoni, David Cheikhi:
From Average Embeddings To Nearest Neighbor Search. CoRR abs/2105.05761 (2021) - [i35]Alexandr Andoni, Daniel Beaglehole:
Learning to Hash Robustly, with Guarantees. CoRR abs/2108.05433 (2021) - [i34]Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein:
Estimating the Longest Increasing Subsequence in Nearly Optimal Time. CoRR abs/2112.05106 (2021) - 2020
- [c57]Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff:
Streaming Complexity of SVMs. APPROX-RANDOM 2020: 50:1-50:22 - [c56]Alexandr Andoni, Negev Shekel Nosatzki:
Edit Distance in Near-Linear Time: it's a Constant Factor. FOCS 2020: 990-1001 - [c55]Alexandr Andoni, Clifford Stein, Peilin Zhong:
Parallel approximate undirected shortest paths via low hop emulators. STOC 2020: 322-335 - [i33]Alexandr Andoni, Negev Shekel Nosatzki:
Edit Distance in Near-Linear Time: it's a Constant Factor. CoRR abs/2005.07678 (2020) - [i32]Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff:
Streaming Complexity of SVMs. CoRR abs/2007.03633 (2020)
2010 – 2019
- 2019
- [c54]Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, Kiran Vodrahalli:
Attribute-efficient learning of monomials over highly-correlated variables. ALT 2019: 127-161 - [c53]Alexandr Andoni, Clifford Stein, Peilin Zhong:
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. ICALP 2019: 14:1-14:16 - [c52]Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki:
Two Party Distribution Testing: Communication and Security. ICALP 2019: 15:1-15:16 - [c51]Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow:
On Solving Linear Systems in Sublinear Time. ITCS 2019: 3:1-3:19 - [i31]Alexandr Andoni, Clifford Stein, Peilin Zhong:
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. CoRR abs/1905.00850 (2019) - [i30]Alexandr Andoni, Clifford Stein, Peilin Zhong:
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. CoRR abs/1911.01956 (2019) - 2018
- [j8]Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn:
Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. 47(3): 890-916 (2018) - [c50]Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS 2018: 159-169 - [c49]Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong:
Parallel Graph Connectivity in Log Diameter Rounds. FOCS 2018: 674-685 - [c48]Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong:
Subspace Embedding and Linear Regression with Orlicz Norm. ICML 2018: 224-233 - [c47]Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Data-dependent hashing via nonlinear spectral gaps. STOC 2018: 787-800 - [i29]Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, Peilin Zhong:
Parallel Graph Connectivity in Log Diameter Rounds. CoRR abs/1805.03055 (2018) - [i28]Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong:
Subspace Embedding and Linear Regression with Orlicz Norm. CoRR abs/1806.06430 (2018) - [i27]Alexandr Andoni, Piotr Indyk, Ilya P. Razenshteyn:
Approximate Nearest Neighbor Search in High Dimensions. CoRR abs/1806.09823 (2018) - [i26]Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price:
Batch Sparse Recovery, or How to Leverage the Average Sparsity. CoRR abs/1807.08478 (2018) - [i25]Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow:
On Solving Linear Systems in Sublinear Time. CoRR abs/1809.02995 (2018) - [i24]Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki:
Two Party Distribution Testing: Communication and Security. CoRR abs/1811.04065 (2018) - [i23]Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki:
Two Party Distribution Testing: Communication and Security. IACR Cryptol. ePrint Arch. 2018: 1086 (2018) - 2017
- [j7]Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk:
Editorial. ACM Trans. Algorithms 13(2): 18:1 (2017) - [c46]Alexandr Andoni, Daniel J. Hsu, Kevin Shi, Xiaorui Sun:
Correspondence retrieval. COLT 2017: 105-126 - [c45]Alexandr Andoni:
High frequency moments via max-stability. ICASSP 2017: 6364-6368 - [c44]Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten:
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. SODA 2017: 47-66 - [c43]Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki:
LSH Forest: Practical Algorithms Made Theoretical. SODA 2017: 67-78 - [c42]Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Approximate near neighbors for general symmetric norms. STOC 2017: 902-913 - [i22]Alexandr Andoni, Javad Ghaderi, Daniel J. Hsu, Dan Rubenstein, Omri Weinstein:
Coding with asymmetric prior knowledge. CoRR abs/1707.04875 (2017) - 2016
- [j6]Alexandr Andoni, Huy L. Nguyên:
Width of Points in the Streaming Model. ACM Trans. Algorithms 12(1): 5:1-5:10 (2016) - [c41]Alexandr Andoni, Ilya P. Razenshteyn:
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. SoCG 2016: 9:1-9:11 - [c40]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: 31-43 - [c39]Alexandr Andoni, Assaf Naor, Ofer Neiman:
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. ICALP 2016: 83:1-83:14 - [c38]Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. ITCS 2016: 311-319 - [p3]Alexandr Andoni:
High-Dimensional Computational Geometry. Handbook of Big Data 2016: 105-123 - [i21]Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten:
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. CoRR abs/1605.02701 (2016) - [i20]Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten:
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. CoRR abs/1608.03580 (2016) - [i19]Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Approximate Near Neighbors for General Symmetric Norms. CoRR abs/1611.06222 (2016) - 2015
- [c37]Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt:
Practical and Optimal LSH for Angular Distance. NIPS 2015: 1225-1233 - [c36]Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn:
Sketching and Embedding are Equivalent for Norms. STOC 2015: 479-488 - [c35]Alexandr Andoni, Ilya P. Razenshteyn:
Optimal Data-Dependent Hashing for Approximate Near Neighbors. STOC 2015: 793-801 - [i18]Alexandr Andoni, Ilya P. Razenshteyn:
Optimal Data-Dependent Hashing for Approximate Near Neighbors. CoRR abs/1501.01062 (2015) - [i17]Alexandr Andoni, Ilya P. Razenshteyn:
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. CoRR abs/1507.04299 (2015) - [i16]Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt:
Practical and Optimal LSH for Angular Distance. CoRR abs/1509.02897 (2015) - [i15]Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. CoRR abs/1511.06099 (2015) - 2014
- [c34]Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer:
Spectral Approaches to Nearest Neighbor Search. FOCS 2014: 581-590 - [c33]Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang:
Learning Polynomials with Neural Networks. ICML 2014: 1908-1916 - [c32]Alexandr Andoni, Anupam Gupta, Robert Krauthgamer:
Towards (1 + ∊)-Approximate Flow Sparsifiers. SODA 2014: 279-293 - [c31]Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang:
Learning Sparse Polynomial Functions. SODA 2014: 500-510 - [c30]Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn:
Beyond Locality-Sensitive Hashing. SODA 2014: 1018-1028 - [c29]Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev:
Parallel algorithms for geometric graph problems. STOC 2014: 574-583 - [i14]Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev:
Parallel Algorithms for Geometric Graph Problems. CoRR abs/1401.0042 (2014) - [i13]Alexandr Andoni, Robert Krauthgamer, David P. Woodruff:
The Sketching Complexity of Graph Cuts. CoRR abs/1403.7058 (2014) - [i12]Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer:
Spectral Approaches to Nearest Neighbor Search. CoRR abs/1408.0751 (2014) - [i11]Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn:
Sketching and Embedding are Equivalent for Norms. CoRR abs/1411.2577 (2014) - 2013
- [j5]Alexandr Andoni, Atri Rudra:
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword. Theory Comput. 9: 437-439 (2013) - [c28]Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu:
Tight Lower Bound for Linear Sketches of Moments. ICALP (1) 2013: 25-32 - [c27]Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh:
Shift Finding in Sub-Linear Time. SODA 2013: 457-465 - [c26]Alexandr Andoni, Huy L. Nguyen:
Eigenvalues of a matrix in the streaming model. SODA 2013: 1729-1737 - [c25]Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat:
Homomorphic fingerprints under misalignments: sketching edit and shift distances. STOC 2013: 931-940 - [i10]Alexandr Andoni, Rina Panigrahy:
A Differential Equations Approach to Optimizing Regret Trade-offs. CoRR abs/1305.1359 (2013) - [i9]Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn:
Beyond Locality-Sensitive Hashing. CoRR abs/1306.1547 (2013) - [i8]Alexandr Andoni, Huy L. Nguyen, Yury Polyanskiy, Yihong Wu:
Tight Lower Bound for Linear Sketches of Moments. CoRR abs/1306.6295 (2013) - [i7]Alexandr Andoni, Anupam Gupta, Robert Krauthgamer:
Towards (1+ε)-Approximate Flow Sparsifiers. CoRR abs/1310.3252 (2013) - 2012
- [j4]Alexandr Andoni, Krzysztof Onak:
Approximating Edit Distance in Near-Linear Time. SIAM J. Comput. 41(6): 1635-1648 (2012) - [j3]Alexandr Andoni, Robert Krauthgamer:
The smoothed complexity of edit distance. ACM Trans. Algorithms 8(4): 44:1-44:25 (2012) - [c24]Alexandr Andoni, Huy L. Nguyen:
Width of points in the streaming model. SODA 2012: 447-452 - 2011
- [c23]Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen:
Near Linear Lower Bound for Dimension Reduction in L1. FOCS 2011: 315-323 - [c22]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Streaming Algorithms via Precision Sampling. FOCS 2011: 363-372 - [c21]Alexandr Andoni:
Nearest Neighbor Search in High-Dimensional Spaces. MFCS 2011: 1 - [i6]Alexandr Andoni, Krzysztof Onak:
Approximating Edit Distance in Near-Linear Time. CoRR abs/1109.5635 (2011) - 2010
- [j2]Alexandr Andoni, Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance. SIAM J. Comput. 39(6): 2398-2429 (2010) - [c20]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS 2010: 377-386 - [c19]Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch:
Global Alignment of Molecular Sequences via Ancestral State Reconstruction. ICS 2010: 358-369 - [c18]Alexandr Andoni, Huy L. Nguyen:
Near-Optimal Sublinear Time Algorithms for Ulam Distance. SODA 2010: 76-86 - [c17]Alexandr Andoni, T. S. Jayram, Mihai Patrascu:
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. SODA 2010: 184-192 - [p2]Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243 - [p1]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Property Testing 2010: 244-252 - [i5]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. CoRR abs/1005.4033 (2010) - [i4]Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
Streaming Algorithms from Precision Sampling. CoRR abs/1011.1263 (2010)
2000 – 2009
- 2009
- [b1]Alexandr Andoni:
NN search : the old, the new, and the impossible. Massachusetts Institute of Technology, Cambridge, MA, USA, 2009 - [c16]Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff:
Efficient Sketches for Earth-Mover Distance, with Applications. FOCS 2009: 324-330 - [c15]Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
External Sampling. ICALP (1) 2009: 83-94 - [c14]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen:
Approximate line nearest neighbor in high dimensions. SODA 2009: 293-301 - [c13]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Overcoming the l1 non-embeddability barrier: algorithms for product metrics. SODA 2009: 865-874 - [c12]Alexandr Andoni, Krzysztof Onak:
Approximating edit distance in near-linear time. STOC 2009: 199-204 - [i3]Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sébastien Roch:
Global Alignment of Molecular Sequences via Ancestral State Reconstruction. CoRR abs/0912.2577 (2009) - 2008
- [j1]Alexandr Andoni, Piotr Indyk:
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008) - [c11]Alexandr Andoni, Dorian Croitoru, Mihai Patrascu:
Hardness of Nearest Neighbor under L-infinity. FOCS 2008: 424-433 - [c10]Alexandr Andoni, Robert Krauthgamer:
The Smoothed Complexity of Edit Distance. ICALP (1) 2008: 357-369 - [c9]Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar:
Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03). SIGMOD Conference 2008: 1375-1376 - [c8]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Earth mover distance over high-dimensional spaces. SODA 2008: 343-352 - [i2]Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy:
Better Bounds for Frequency Moments in Random-Order Streams. CoRR abs/0808.2222 (2008) - 2007
- [c7]Alexandr Andoni, Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance [Extended Abstract]. FOCS 2007: 724-734 - [c6]Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie:
Testing k-wise and almost k-wise independence. STOC 2007: 496-505 - [i1]Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Earth Mover Distance over High-Dimensional Spaces. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c5]Alexandr Andoni, Piotr Indyk, Mihai Patrascu:
On the Optimality of the Dimensionality Reduction Method. FOCS 2006: 449-458 - [c4]Alexandr Andoni, Piotr Indyk:
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. FOCS 2006: 459-468 - [c3]Alexandr Andoni, Piotr Indyk:
Efficient algorithms for substring near neighbor problem. SODA 2006: 1203-1212 - 2005
- [c2]Alexandr Andoni, Jessica Staddon:
Graceful service degradation (or, how to know your payment is late). EC 2005: 9-18 - 2003
- [c1]Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova:
Lower bounds for embedding edit distance into normed spaces. SODA 2003: 523-526
Coauthor Index