Alexandr Andoni

Manuscripts:

• "The Query Complexity of Edit Distance" (with Robert Krauthgamer and Krzysztof Onak). Manuscript, 2009.
  
  
• "Phylogenetic Reconstruction with Insertions and Deletions" (with Mark Braverman and Avinatan Hassidim). Manuscript, 2009.
  
  
• "Distance Estimation Protocols for General Metrics" (with Robert Krauthgamer). Manuscript, 2008.
  
  
• "Block Heavy Hitters" (with Khanh Do Ba and Piotr Indyk). MIT Technical Report MIT-CSAIL-TR-2008-024, 2008.
  download: available here.
  
  

Publications:

• "Global Alignment of Molecular Sequences via Ancestral State Reconstruction" (with Constantinos Daskalakis, Avinatan Hassidim, and Sebastien Roch). Accepted to ICS'10, 2010.
  
  
• "Lower bounds for Edit Distance and Product Metrics via Poincare-Type Inequalities" (with T.S. Jayram and Mihai Pătraşcu). In Proceedings of the Symposium on Discrete Algorithms (SODA'10), 2010. To appear.
  download: [.pdf, .ps].
  
  
• "Near-Optimal Sublinear Time Algorithms for Ulam Distance" (with Huy L. Nguyen). In Proceedings of the Symposium on Discrete Algorithms (SODA'10), 2010. To appear.
  download: [.pdf, .ps].
  
  
• "Efficient sketches for Earth-Mover Distance, with applications" (with Khanh Do Ba, Piotr Indyk, and David Woodruff). In Proceedings of Symposium on Foundations of Computer Science (FOCS'09), 2009.
  download: [.pdf, .ps].
  
  
• "External Sampling" (with Piotr Indyk, Krzysztof Onak, and Ronitt Rubinfeld). In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP'09), 2009.
  download: [.pdf, .ps].
  
  
• "Approximating Edit Distance in Near-Linear Time" (with Krzysztof Onak). In Proceedings of the Symposium on Theory of Computing (STOC'09), 2009. Invited to SICOMP special issue of STOC'09.
  download: preliminary journal version [.pdf, .ps]
  
  
• "Approximate Line Nearest Neighbor in High Dimensions" (with Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen). In Proceedings of the Symposium on Discrete Algorithms (SODA'09), 2009.
  download: [.pdf, .ps].
  
  
• "Overcoming the L1 Non-Embeddability Barrier: Algorithms for Product Metrics" (with Piotr Indyk and Robert Krauthgamer). In Proceedings of the Symposium on Discrete Algorithms (SODA'09), 2009.
  download: [.pdf, .ps]. For temporary "full version", see Chapter 5 in the PhD thesis.
  
  
• "Hardness of Nearest Neighbor under L-infinity" (with Dorian Croitoru and Mihai Pătraşcu). In Proceedings of Symposium on Foundations of Computer Science (FOCS'08), 2008.
  download: [.pdf, .ps].
  
  
• "The Smoothed Complexity of Edit Distance" (with Robert Krauthgamer). In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP'08), 2008. Full version in submission.
  download: [.pdf, .ps]
  
  
• "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with Piotr Indyk). Communications of the ACM, vol. 51, no. 1, 2008, pp. 117-122.
  download: local .ps copy, or directly from CACM (for free). CACM disclaimer.
  
  
• "Earth Mover Distance over High-Dimensional Spaces" (with Piotr Indyk and Robert Krauthgamer). In Proceedings of the Symposium on Discrete Algorithms(SODA'08), 2008. Previously ECCC TR07-048.
  download: [.pdf, .ps]
  
  
• "The Computational Hardness of Estimating Edit Distance" (with Robert Krauthgamer). Accepted to SIAM J. on Computing (FOCS special issue). Extended abstract in Proceedings of Symposium on Foundations of Computer Science (FOCS'07), 2007.
  download: preliminary journal version [.pdf, .ps]
  
  
• "Testing k-wise and Almost k-wise independence" (with Noga Alon, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie). In Proceedings of ACM Symposium on Theory of Computing (STOC'07), 2007. Full version in preparation.
  download: [.pdf, .ps]
  
  
• "Locality-sensitive hashing using stable distributions" (with Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni), in "Nearest Neighbor Methods in Learning and Vision: Theory and Practice", T. Darrell and P. Indyk and G. Shakhnarovich (eds.), MIT Press, 2006. See also the Intro to that book.
  download: [.pdf, .ps]
  
  
• "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with Piotr Indyk). In Proceedings of the Symposium on Foundations of Computer Science (FOCS'06), 2006.
  download: [.pdf, .ps]. For current "full version", see Chapter 3 in the PhD thesis.
  
  
• "On the Optimality of the Dimensionality Reduction Method" (with Mihai Pătraşcu and Piotr Indyk). In Proceedings of the Symposium on Foundations of Computer Science (FOCS'06), 2006.
  download: [.pdf, .ps]
  
  
• "Efficient Algorithms for Substring Near Neighbor Problem" (with Piotr Indyk). In Proceedings of the Symposium on Discrete Algorithyms (SODA'06), 2006. For a full version, see my Master's thesis below.
  download: [.pdf, .ps, .ppt talk]
  
  
• "Graceful Service Degradation (or, How to Know Your Payment Is Late)" (with Jessica Staddon). Proceedings of the 6th ACM Conference on Electronic Commerce (EC'05) , Vancouver, June 2005.
  download: [.pdf, .ps, .ppt talk]
  
  
• "An evaluation of exhaustive testing for data structures" (with Darko Marinov, Dumitru Daniliuc, Sarfraz Khurshid, and Martin Rinard). Technical Report MIT-LCS-TR-921, MIT CSAIL, Cambridge, MA, September 2003.
  download: [.pdf, .ps]
  
  
• "Lower Bounds for Embedding of Edit Distance into Normed Spaces" (with Michel Deza, Anupam Gupta, Piotr Indyk, and Sofya Raskhodnikova). Proceedings of the 14th Symposium on Discrete Algorithms (SODA'03) , 2003.
  download: [.pdf, .ps, .ppt talk]

Theses:

An undergrad project paper: