Ilya P. Razenshteyn

According to our database, Ilya P. Razenshteyn authored at least 51 papers between 2010 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

Learning Space Partitions for Nearest Neighbor Search.

Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner

IEEE Data Eng. Bull., 2023

2022

Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm.

Meena Jagadeesan, Ilya P. Razenshteyn, Suriya Gunasekar

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Approximate Nearest Neighbors Beyond Space Partitions.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Maliciously Secure Matrix Multiplication with Applications to Private Deep Learning.

Hao Chen, Miran Kim, Ilya P. Razenshteyn, Dragos Rotaru, Yongsoo Song, Sameer Wagh

IACR Cryptol. ePrint Arch., 2020

A Study of Performance of Optimal Transport.

Yihe Dong, Yu Gao, Richard Peng, Ilya P. Razenshteyn, Saurabh Sawlani

CoRR, 2020

Non-adaptive adaptive sampling on turnstile streams.

Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Randomized Smoothing of All Shapes and Sizes.

Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya P. Razenshteyn, Jerry Li

Proceedings of the 37th International Conference on Machine Learning, 2020

Scalable Nearest Neighbor Search for Optimal Transport.

Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner

Proceedings of the 37th International Conference on Machine Learning, 2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing.

Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, Ilya P. Razenshteyn

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search.

Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya P. Razenshteyn, M. Sadegh Riazi

IACR Cryptol. ePrint Arch., 2019

Scalable Nearest Neighbor Search for Optimal Transport.

Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner

CoRR, 2019

Learning Sublinear-Time Indexing for Nearest Neighbor Search.

Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner

CoRR, 2019

Performance of Johnson-Lindenstrauss transform for <i>k</i>-means and <i>k</i>-medians clustering.

Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers.

Hadi Salman, Jerry Li, Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, Greg Yang

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Adversarial examples from computational constraints.

Sébastien Bubeck, Yin Tat Lee, Eric Price, Ilya P. Razenshteyn

Proceedings of the 36th International Conference on Machine Learning, 2019

On Mean Estimation for General Norms with Statistical Queries.

Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the Conference on Learning Theory, 2019

2018

Sketching and Embedding are Equivalent for Norms.

Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn

SIAM J. Comput., 2018

Adversarial Examples from Cryptographic Pseudo-Random Generators.

Sébastien Bubeck, Yin Tat Lee, Eric Price, Ilya P. Razenshteyn

CoRR, 2018

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering.

Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

CoRR, 2018

Approximate Nearest Neighbor Search in High Dimensions.

Alexandr Andoni, Piotr Indyk, Ilya P. Razenshteyn

CoRR, 2018

Adversarial examples from computational constraints.

Sébastien Bubeck, Eric Price, Ilya P. Razenshteyn

CoRR, 2018

Nonlinear dimension reduction via outer Bi-Lipschitz extensions.

Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

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

Data-dependent hashing via nonlinear spectral gaps.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

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

Hölder Homeomorphisms and Approximate Nearest Neighbors.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

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

2017

High-dimensional similarity search and sketching: algorithms and hardness.

Ilya P. Razenshteyn

PhD thesis, 2017

Approximate near neighbors for general symmetric norms.

Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

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

LSH Forest: Practical Algorithms Made Theoretical.

Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki

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

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

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

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

Practical Data-Dependent Metric Compression with Provable Guarantees.

Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

2016

Restricted Isometry Property for General p-Norms.

Zeyuan Allen Zhu, Rati Gelashvili, Ilya P. Razenshteyn

IEEE Trans. Inf. Theory, 2016

Approximate Near Neighbors for General Symmetric Norms.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors.

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

Weighted low rank approximations with provable guarantees.

Ilya P. Razenshteyn, Zhao Song, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Nearly-optimal bounds for sparse recovery in generic norms, with applications to <i>k</i>-median sketching.

Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Complexity of Inner Product Similarity Join.

Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, Francesco Silvestri

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

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

Alexandr Andoni, Ilya P. Razenshteyn

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

2015

An exact combinatorial algorithm for minimum graph bisection.

Daniel Delling, Daniel Fleischman, Andrew V. Goldberg, Ilya P. Razenshteyn, Renato F. Werneck

Math. Program., 2015

Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching.

Arturs Backurs, Piotr Indyk, Eric Price, Ilya P. Razenshteyn, David P. Woodruff

CoRR, 2015

Optimal Data-Dependent Hashing for Approximate Near Neighbors.

Alexandr Andoni, Ilya P. Razenshteyn

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

Practical and Optimal LSH for Angular Distance.

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, Ludwig Schmidt

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

Robust Hierarchical k-Center Clustering.

Silvio Lattanzi, Stefano Leonardi, Vahab S. Mirrokni, Ilya P. Razenshteyn

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Beyond Locality-Sensitive Hashing.

Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn

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

2013

Separating Hierarchical and General Hub Labelings.

Andrew V. Goldberg, Ilya P. Razenshteyn, Ruslan Savchenko

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

On Model-Based RIP-1 Matrices.

Piotr Indyk, Ilya P. Razenshteyn

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

2012

On Epsilon-Nets, Distance Oracles, and Metric Embeddings

Ilya P. Razenshteyn

CoRR, 2012

Exact Combinatorial Branch-and-Bound for Graph Bisection.

Daniel Delling, Andrew V. Goldberg, Ilya P. Razenshteyn, Renato Fonseca F. Werneck

Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011

Not every domain of a plain decompressor contains the domain of a prefix-free one.

Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen

Theor. Comput. Sci., 2011

Common information revisited

Ilya P. Razenshteyn

CoRR, 2011

Graph Partitioning with Natural Cuts.

Daniel Delling, Andrew V. Goldberg, Ilya P. Razenshteyn, Renato Fonseca F. Werneck

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

2010

Triangle-Free 2-Matchings Revisited.

Maxim A. Babenko, Alexey Gusakov, Ilya P. Razenshteyn

Discret. Math. Algorithms Appl., 2010

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks.

Maxim A. Babenko, Ignat I. Kolesnichenko, Ilya P. Razenshteyn

Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010