Alexandr Andoni

Manuscripts:

• "High frequency moments via max-stability". See also my blog post. Manuscript, 2012.
  
  
• "Phylogenetic Reconstruction with Insertions and Deletions" (with Mark Braverman and Avinatan Hassidim). Manuscript, 2010.
  
  
• "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:

• "Tight Lower Bound for Linear Sketches of Moments" (joint with Huy L. Nguyen, Yury Polyanskiy, and Yihong Wu). Accepted to ICALP, 2013.
  
  
• "Homomorphic Fingerprints under Misalignments: Sketching Edit and Shift Distances" (joint with Assaf Goldberger, Andrew McGregor, and Ely Porat). Accepted to STOC'13.
  
  
• "Shift Finding in Sub-linear Time" (joint with Haitham Hassanieh, Piotr Indyk, and Dina Katabi). In SODA'13.
  
  
• "Eigenvalues of a Matrix in the Streaming Model" (joint with Huy L. Nguyen). In SODA'13.
  
  
• "Width of Points in the Streaming Model" (with Huy L. Nguyen). Accepted to Transactions on Algorithms special issue of SODA'12. Previously in SODA'12.
  download: journal version.
  
  
• "Near Linear Lower Bound for Dimension Reduction in L1" (with Moses Charikar, Ofer Neiman, and Huy L. Nguyen). In FOCS'11.
  download: conference version.
  
  
• "Streaming Algorithms via Precision Sampling" (with Robert Krauthgamer and Krzysztof Onak). In FOCS'11. Full version on arXiv:1011.1263.
  download: arXiv version, conference version.
  
  
• "Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity" (with Robert Krauthgamer and Krzysztof Onak). In Proceedings of Symposium on Foundations of Computer Science (FOCS'10), 2010. Invited to SICOMP special issue (declined).
  download: arXiv version, conference version.
  
  
• "Global Alignment of Molecular Sequences via Ancestral State Reconstruction" (with Constantinos Daskalakis, Avinatan Hassidim, and Sebastien Roch). Stochastic Processes and their Applications 122 (2012), pp. 3852--3874. Extended abstract in Proceedings of the Symposium on Innovations in Computer Science (ICS'10), 2010.
  download: [journal version]
  
  
• "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.
  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.
  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. SIAM J. Comp. (SICOMP), special issue of STOC'09. Previously in STOC'09, arXiv:1109.5635.
  download: journal version [.pdf, .ps], arXiv version.
  
  
• "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 TALG. Previously in Proceedings of International Colloquium on Automata, Languages and Programming (ICALP'08), 2008.
  download: [journal version, conference version].
  
  
• "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). SIAM J. on Computing (FOCS'07 special issue), vol.39, no.6, 2010. Extended abstract in Proceedings of Symposium on Foundations of Computer Science (FOCS'07), 2007.
  download: 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: