1. S. Bubeck, E. Price and IR, Adversarial examples from computational constraints, 2018 (arXiv).
  2. A. Andoni, A. Naor, A. Nikolov, IR and E. Waingarten, Hölder Homeomorphisms and Approximate Nearest Neighbors, 2018.


  1. A. Andoni, A. Naor, A. Nikolov, IR and E. Waingarten, Data-Dependent Hashing via Nonlinear Spectral Gaps, STOC, 2018 (local copy).
  2. S. Mahabadi, K. Makarychev, Y. Makarychev and IR, Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions, STOC, 2018.
  3. P. Indyk, IR and T. Wagner, Practical Data-Dependent Metric Compression with Provable Guarantees, NIPS, 2017 (arXiv, code).
  4. A. Andoni, H. Nguyen, A. Nikolov, IR and E. Waingarten, Approximate Near Neighbors for General Symmetric Norms, STOC, 2017 (arXiv, long slides).
  5. A. Andoni, IR and N. Shekel Nosatzki, LSH Forest: Practical Algorithms Made Theoretical, SODA, 2017 (local copy, short slides).
    Invited to Highlights of Algorithms (HALG 2018)
  6. A. Andoni, T. Laarhoven, IR and E. Waingarten, Optimal Hashing-based Time–Space Trade-offs for Approximate Near Neighbors, SODA, 2017 (arXiv, long slides).
    Invited to the special issue of ACM Transactions on Algorithms
  7. T.D. Ahle, R. Pagh, IR and F. Silvestri, On the Complexity of Inner Product Similarity Join, PODS, 2016 (arXiv).
  8. A. Andoni and IR, Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing, SoCG, 2016 (arXiv, short slides).
    Invited to Highlights of Algorithms (HALG 2017)
  9. IR, Z. Song and D. Woodruff, Weighted Low Rank Approximations with Provable Guarantees, STOC, 2016 (local copy).
  10. A. Backurs, P. Indyk, IR and D. Woodruff, Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching, SODA, 2016 (arXiv).
  11. A. Andoni, P. Indyk, T. Laarhoven, IR and L. Schmidt, Practical and Optimal LSH for Angular Distance, NIPS, 2015 (arXiv, long slides, poster, code).
  12. A. Andoni and IR, Optimal Data-Dependent Hashing for Approximate Near Neighbors, STOC, 2015 (arXiv, five-minute talk, video, long slides, short slides).
    Invited to Highlights of Algorithms (HALG 2016)
  13. S. Lattanzi, S. Leonardi, V. Mirrokni and IR, Robust Hierarchical $k$-Center Clustering, ITCS, 2015 (slides).
  14. A. Andoni, P. Indyk, H. Nguyen and IR, Beyond Locality-Sensitive Hashing, SODA, 2014 (arXiv, blog post, long slides, short slides, video, poster).
  15. A. Goldberg, IR and R. Savchenko, Separating Hierarchical and General Hub Labelings, MFCS, 2013 (arXiv).
  16. P. Indyk and IR, On Model-Based RIP-1 Matrices, ICALP, 2013 (arXiv, slides).
  17. D. Delling, A. Goldberg, IR and R. Werneck, Graph Partitioning with Natural Cuts, IPDPS, 2011 (technical report, slides).
  18. M. Babenko, I. Kolesnichenko and IR, A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks, SOFSEM, 2010 (arXiv).


  1. A. Andoni, R. Krauthgamer and IR, Sketching and Embedding are Equivalent for Norms, SIAM Journal on Computing, special issue for STOC 2015, accepted; preliminary version appeared in STOC, 2015 (arXiv, blog post, long slides, short slides, poster).
    Invited to Highlights of Algorithms (HALG 2016)
  2. Z. Allen-Zhu, R. Gelashvili and IR, Restricted Isometry Property for General p-Norms, IEEE Transactions on Information Theory, Vol. 62, Issue 10, pp. 5839–5854, 2016; preliminary version appeared in SoCG 2015 (arXiv, slides).
  3. D. Delling, D. Fleischman, A. Goldberg, IR and R. Werneck, An Exact Combinatorial Algorithm for Minimum Graph Bisection, Mathematical Programming, Vol. 153, Issue 2, pp. 417–458, 2015; preliminary versions appeared in ALENEX 2012 and ESA 2012 (local copy).
  4. M. Andreev, IR and A. Shen, Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One, Theoretical Computer Science, Vol. 412, pp. 482–486, 2011; preliminary version appeared in CiE 2010 (arXiv, slides).
  5. M. Babenko, A. Gusakov and IR, Triangle-Free 2-Matchings Revisited, Discrete Mathematics, Algorithms and Applications, special issue for COCOON 2010, Vol. 2, Issue 4, pp. 643–654, 2010; preliminary version appeared in COCOON 2010 (arXiv).


  1. Ph.D. Thesis (MIT): High-Dimensional Similarity Search and Sketching: Algorithms and Hardness, 2017 (local copy).
    George W. Sprowls Award for the outstanding Ph.D. theses in Computer Science
    EATCS Distinguished Dissertation Award
  2. S.M. Thesis (MIT): Beyond Locality-Sensitive Hashing, 2014 (DSpace@MIT).
  3. M.S. Thesis (Moscow State University): Covering Shortest Paths in Undirected Graphs, 2012 (local copy).
  4. Term paper: On Epsilon-Nets, Distance Oracles, and Metric Embeddings, 2012 (arXiv).
  5. Term paper: Common information revisited, 2011 (arXiv).

© 2015–2018