# Alexandr Andoni

According to our database

Collaborative distances:

^{1}, Alexandr Andoni authored at least 60 papers between 2003 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

On Solving Linear Systems in Sublinear Time.

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

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

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

Two Party Distribution Testing: Communication and Security.

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

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

Proceedings of the Algorithmic Learning Theory, 2019

2018

Data-dependent hashing via nonlinear spectral gaps.

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

Subspace Embedding and Linear Regression with Orlicz Norm.

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

Parallel Graph Connectivity in Log Diameter Rounds.

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

Hölder Homeomorphisms and Approximate Nearest Neighbors.

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

2017

Editorial.

ACM Trans. Algorithms, 2017

Approximate near neighbors for general symmetric norms.

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

LSH Forest: Practical Algorithms Made Theoretical.

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

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

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

High frequency moments via max-stability.

Proceedings of the 2017 IEEE International Conference on Acoustics, 2017

Correspondence retrieval.

Proceedings of the 30th Conference on Learning Theory, 2017

2016

On Sketching Quadratic Forms.

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

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

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

Interacting with Large Distributed Datasets Using Sketch.

Proceedings of the EGPGV16: Eurographics Symposium on Parallel Graphics and Visualization, 2016

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

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

High-Dimensional Computational Geometry.

Proceedings of the Handbook of Big Data., 2016

2015

Optimal Data-Dependent Hashing for Approximate Near Neighbors.

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

Sketching and Embedding are Equivalent for Norms.

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

Practical and Optimal LSH for Angular Distance.

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

2014

Parallel algorithms for geometric graph problems.

Proceedings of the Symposium on Theory of Computing, 2014

Learning Sparse Polynomial Functions.

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

Beyond Locality-Sensitive Hashing.

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

Towards (1 +

*∊*)-Approximate Flow Sparsifiers.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Learning Polynomials with Neural Networks.

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

Spectral Approaches to Nearest Neighbor Search.

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

2013

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

Theory of Computing, 2013

Homomorphic fingerprints under misalignments: sketching edit and shift distances.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Eigenvalues of a matrix in the streaming model.

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

Shift Finding in Sub-Linear Time.

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

Tight Lower Bound for Linear Sketches of Moments.

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

2012

Width of points in the streaming model.

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Nearest Neighbor Search in High-Dimensional Spaces.

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Streaming Algorithms via Precision Sampling.

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

Near Linear Lower Bound for Dimension Reduction in L1.

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

2010

The Computational Hardness of Estimating Edit Distance.

SIAM J. Comput., 2010

Near-Optimal Sublinear Time Algorithms for Ulam Distance.

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.

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

Sublinear Algorithms in the External Memory Model.

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

Global Alignment of Molecular Sequences via Ancestral State Reconstruction.

Proceedings of the Innovations in Computer Science, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

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

2009

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

PhD thesis, 2009

Approximating edit distance in near-linear time.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Approximate line nearest neighbor in high dimensions.

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

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

External Sampling.

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

Efficient Sketches for Earth-Mover Distance, with Applications.

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

2008

Earth mover distance over high-dimensional spaces.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

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

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

The Smoothed Complexity of Edit Distance.

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Hardness of Nearest Neighbor under L-infinity.

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

2007

Testing k-wise and almost k-wise independence.

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

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

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

2006

Efficient algorithms for substring near neighbor problem.

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

On the Optimality of the Dimensionality Reduction Method.

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

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions.

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).

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

2003

Lower bounds for embedding edit distance into normed spaces.

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