Alexandr Andoni

Manuscripts:

• "Approximate Line Nearest Neighbor in High Dimensions" (with Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen). Manuscript, 2008.
  
  
• "External Sampling" (with Piotr Indyk, Krzysztof Onak, and Ronitt Rubinfeld). Manuscript, 2008.
  
  
• "Overcoming the L1 Non-Embeddability Barrier: Algorithms for Product Metrics" (with Piotr Indyk and Robert Krauthgamer). Manuscript, 2008.
  
  
• "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:

• Hardness of Nearest Neighbor under L-infinity" (with Dorian Croitoru and Mihai Pătraşcu). Accepted to FOCS 2008.
  download: [.pdf, .ps].
  
  
• "The Smoothed Complexity of Edit Distance" (with Robert Krauthgamer). Accepted to ICALP, 2008. Full version is being worked on.
  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). Invited 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 is being worked on.
  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. Full version to appear in future.
  download: [.pdf, .ps]
  
  
• "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. Full version to appear in future.
  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]

M.Eng. Thesis:

An undergrad project paper: