Publications
- Unveiling Transformers with LEGO: a synthetic reasoning task
with Yi Zhang, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar and Tal Wagner
- Differentially Private Model Compression
with Fatemehsadat Mireshghallah, Huseyin A Inan, Lukas Wutschitz and Janardhan Kulkarni
- Differentially Private Fine-tuning of Language Models
with Da Yu, Saurabh Naik, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin and Huishuai Zhang
in the 10th International Conference on Learning Representations, ICLR 2022
- A note on more efficient architectures for NLP
with Mingda Chen and Kevin Gimpel
- Data-to-text Generation by Splicing Together Nearest Neighbors
with Sam Wiseman and Karl Stratos
in the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021
- Faster Kernel Matrix Algebra via Density Estimation
with Piotr Indyk, Cameron Musco and Tal Wagner
in the 38th International Conference on Machine Learning, ICML 2021
- Two-sided Kirszbraun Theorem
with Sepideh Mahabadi, Konstantin Makarychev and Yury Makarychev
in the 37th Symposium on Computational Geometry, SoCG 2021
- Fast and Simple Modular Subset Sum
with Kyriakos Axiotis, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos and Hongxun Wu
in the 4th Symposium on Simplicity in Algorithms, SOSA 2021
- Impossibility Results for Grammar-Compressed Linear Algebra
with Amir Abboud, Karl Bringmann and Marvin Künnemann
in the 34th Conference on Neural Information Processing Systems, NeurIPS 2020
- Scalable Nearest Neighbor Search for Optimal Transport
with Yihe Dong, Piotr Indyk, Ilya Razenshteyn and Tal Wagner
in the 37th International Conference on Machine Learning, ICML 2020
- Active Local Learning
with Avrim Blum and Neha Gupta
in the 33rd Annual Conference on Learning Theory, COLT 2020
- Submodular Clustering in Low Dimensions
with Sariel Har-Peled
in the 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
- Space and Time Efficient Kernel Density Estimation in High Dimensions
with Piotr Indyk and Tal Wagner
in the 33rd Conference on Neural Information Processing Systems, NeurIPS 2019
- Scalable Fair Clustering
with Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian and Tal Wagner
in the 36th International Conference on Machine Learning, ICML 2019
- Efficient Density Evaluation for Smooth Kernels
with Moses Charikar, Piotr Indyk and Paris Siminelakis
in the 59th Symposium on Foundations of Computer Science, FOCS 2018
in the 4th Highlights of Algorithms conference, HALG 2019
- Fast modular subset sum using linear sketching
with Kyriakos Axiotis, Ce Jin, Christos Tzamos and Hongxun Wu
in the 30th Symposium on Discrete Algorithms, SODA 2019
- Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
with Liam Roditty, Gilad Segal, Virginia Vassilevska Williams and Nicole Wein
in the 50th Symposium on Theory of Computing, STOC 2018
SIAM Journal on Computing (SICOMP)
- On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks
with Piotr Indyk and Ludwig Schmidt
in the 31st Conference on Neural Information Processing Systems, NIPS 2017
- Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
with Amir Abboud, Karl Bringmann and Marvin Künnemann
in the 58th Symposium on Foundations of Computer Science, FOCS 2017
- Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
with Christos Tzamos
in the 34th International Conference on Machine Learning, ICML 2017
- Better Approximations for Tree Sparsity in Nearly Linear Time
with Piotr Indyk and Ludwig Schmidt
in the 28th Symposium on Discrete Algorithms, SODA 2017
- Towards Hardness of Approximation for Polynomial Time Problems
with Amir Abboud
in the 8th Innovations in Theoretical Computer Science conference, ITCS 2017
Co-winner of Best Student Paper Award
- Which Regular Expression Patterns are Hard to Match?
with Piotr Indyk
in the 57th Symposium on Foundations of Computer Science, FOCS 2016
- Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces
with Anastasios Sidiropoulos
19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016
- Tight Hardness Results for Maximum Weight Rectangles
with Nishanth Dikkala and Christos Tzamos
in the 43rd International Colloquium on Automata, Languages and Programming, ICALP 2016
- Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
with Krzysztof Onak
in the 35th Symposium on Principles of Database Systems, PODS 2016
- Subtree Isomorphism Revisited
with Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams and Or Zamir
in the 27th Symposium on Discrete Algorithms, SODA 2016
Invited to the special issue
- Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
with Piotr Indyk, Eric Price, Ilya Razenshteyn and David P. Woodruff
in the 27th Symposium on Discrete Algorithms, SODA 2016
- If the Current Clique Algorithms are Optimal, So is Valiant's Parser
with Amir Abboud and Virginia Vassilevska Williams
in the 56th Symposium on Foundations of Computer Science, FOCS 2015
Invited to the special issue
- Tight Hardness Results for LCS and Other Sequence Similarity Measures
with Amir Abboud and Virginia Vassilevska Williams
56th Symposium on Foundations of Computer Science, FOCS 2015
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
with Piotr Indyk
in the 47th Symposium on Theory of Computing, STOC 2015
Invited to the special issue
in the 1st Highlights of Algorithms conference, HALG 2016
- Better embeddings for planar Earth-Mover Distance over sparse sets
with Piotr Indyk
in the 30th Symposium on Computational Geometry, SoCG 2014
- On the sum of L1 influences
with Mohammad Bavarian
in the Computational Complexity Conference, CCC 2014
- Worst Case Analysis of Non-local Games
with Andris Ambainis, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs and Madars Virza
in the 39th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2013
- Optimal quantum query bounds for almost all Boolean functions
with Andris Ambainis, Juris Smotrovs and Ronald de Wolf
in the 30th Symposium on Theoretical Aspects of Computer Science, STACS 2013
- Quantum Strategies Are Better Than Classical in Almost Any XOR Game
with Andris Ambainis, Kaspars Balodis, Dmitrijs Kravcenko, Raitis Ozols, Juris Smotrovs and Madars Virza
in the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012
- Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
with Andris Ambainis, Nikolajs Nahimovs, Raitis Ozols and Alexander Rivosh
in the 7th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2012
- Grover's Algorithm with Errors
with Andris Ambainis, Nikolajs Nahimovs and Alexander Rivosh
in the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2012
Ph.D. Thesis
Below P vs NP: Fine-Grained Hardness for Big Data Problems
MIT, Department of Electrical Engineering and Computer Science, August 2018
George M. Sprowls Award for Best PhD Theses in Computer Science at MIT
EATCS Distinguished Dissertation Award