A. Backurs

Most-cited papers

Differentially Private Fine-tuning of Language Models
Da Yu, Saurabh Naik, A. Backurs, Sivakanth Gopi +8 more
2021International Conference on Learning Representations558 citations Open access
Semantic Scholar
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
A. Backurs, P. Indyk
2014Symposium on the Theory of Computing451 citations Open access
Semantic Scholar
Tight Hardness Results for LCS and Other Sequence Similarity Measures
Amir Abboud, A. Backurs, Virginia Vassilevska Williams
2015IEEE Annual Symposium on Foundations of Computer Science271 citations
Semantic Scholar
Scalable Fair Clustering
A. Backurs, P. Indyk, Krzysztof Onak, B. Schieber +2 more
2019International Conference on Machine Learning237 citations
Semantic Scholar
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
Amir Abboud, A. Backurs, Virginia Vassilevska Williams
2015IEEE Annual Symposium on Foundations of Computer Science140 citations Open access
Semantic Scholar
Which Regular Expression Patterns Are Hard to Match?
A. Backurs, P. Indyk
2015IEEE Annual Symposium on Foundations of Computer Science119 citations Open access
Semantic Scholar
Unveiling Transformers with LEGO: a synthetic reasoning task
Yi Zhang, A. Backurs, Sébastien Bubeck, Ronen Eldan +2 more
2022arXiv.org118 citations Open access
Semantic Scholar
Differentially Private Synthetic Data via Foundation Model APIs 2: Text
Chulin Xie, Zinan Lin, A. Backurs, Sivakanth Gopi +8 more
2024International Conference on Machine Learning103 citations
Semantic Scholar
Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping
Jiyan He, Xuechen Li, Da Yu, Hui-Shuai Zhang +5 more
2022International Conference on Learning Representations75 citations Open access
Semantic Scholar
Space and Time Efficient Kernel Density Estimation in High Dimensions
A. Backurs, P. Indyk, Tal Wagner
2019Neural Information Processing Systems71 citations
Semantic Scholar
Scalable Nearest Neighbor Search for Optimal Transport
A. Backurs, Yihe Dong, P. Indyk, Ilya P. Razenshteyn +1 more
2019International Conference on Machine Learning63 citations
Semantic Scholar
Towards tight approximation bounds for graph diameter and eccentricities
A. Backurs, L. Roditty, Gilad Segal, Virginia Vassilevska Williams +1 more
2018Symposium on the Theory of Computing61 citations Open access
Semantic Scholar
Tight Hardness Results for Maximum Weight Rectangles
A. Backurs, Nishanth Dikkala, Christos Tzamos
2016International Colloquium on Automata, Languages and Programming56 citations
Semantic Scholar
Subtree Isomorphism Revisited
Amir Abboud, A. Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams +1 more
2015ACM-SIAM Symposium on Discrete Algorithms53 citations Open access
Semantic Scholar
Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
A. Backurs, Christos Tzamos
2016International Conference on Machine Learning51 citations
Semantic Scholar
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
A. Ambainis, A. Backurs, N. Nahimovs, Raitis Ozols +1 more
2011Theory of Quantum Computation, Communication, and Cryptography50 citations Open access
Semantic Scholar
On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks
A. Backurs, P. Indyk, Ludwig Schmidt
2017Neural Information Processing Systems45 citations
Semantic Scholar
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve
Amir Abboud, A. Backurs, K. Bringmann, Marvin Künnemann
2017IEEE Annual Symposium on Foundations of Computer Science44 citations Open access
Semantic Scholar
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
Amir Abboud, A. Backurs, Virginia Vassilevska Williams
2015arXiv.org43 citations
Semantic Scholar
Better Approximations for Tree Sparsity in Nearly-Linear Time
A. Backurs, P. Indyk, Ludwig Schmidt
2017ACM-SIAM Symposium on Discrete Algorithms40 citations Open access
Semantic Scholar
Towards Hardness of Approximation for Polynomial Time Problems
Amir Abboud, A. Backurs
2017Information Technology Convergence and Services39 citations
Semantic Scholar
Efficient Density Evaluation for Smooth Kernels
A. Backurs, M. Charikar, P. Indyk, Paris Siminelakis
2018IEEE Annual Symposium on Foundations of Computer Science33 citations
Semantic Scholar
Fast Modular Subset Sum using Linear Sketching
Kyriakos Axiotis, A. Backurs, Ce Jin, Christos Tzamos +1 more
2018ACM-SIAM Symposium on Discrete Algorithms28 citations
Semantic Scholar
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
A. Backurs, P. Indyk, Eric Price, Ilya P. Razenshteyn +1 more
2015ACM-SIAM Symposium on Discrete Algorithms23 citations
Semantic Scholar
Privately Aligning Language Models with Reinforcement Learning
Fan Wu, Huseyin A. Inan, A. Backurs, Varun Chandrasekaran +2 more
2023International Conference on Learning Representations22 citations
Semantic Scholar
Impossibility Results for Grammar-Compressed Linear Algebra
Amir Abboud, A. Backurs, K. Bringmann, Marvin Künnemann
2020Neural Information Processing Systems19 citations
Semantic Scholar
Differentially Private Model Compression
FatemehSadat Mireshghallah, A. Backurs, Huseyin A. Inan, Lukas Wutschitz +1 more
2022Neural Information Processing Systems18 citations Open access
Semantic Scholar
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, A. Backurs, K. Bringmann, Ce Jin +3 more
2020SIAM Symposium on Simplicity in Algorithms18 citations Open access
Semantic Scholar
Grover's Algorithm with Errors
A. Ambainis, A. Backurs, N. Nahimovs, Alexander Rivosh
2012Doctoral Workshop on Mathematical and Engineering Methods in Computer Science17 citations
Semantic Scholar
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
A. Ambainis, A. Backurs, K. Balodis, Dmitrijs Kravčenko +3 more
2011International Colloquium on Automata, Languages and Programming16 citations Open access
Semantic Scholar
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
A. Backurs, L. Roditty, Gilad Segal, Virginia Vassilevska Williams +1 more
2021SIAM journal on computing (Print)15 citations Open access
Semantic Scholar
Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces
A. Backurs, Anastasios Sidiropoulos
2016International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques14 citations
Semantic Scholar
Struct-Bench: A Benchmark for Differentially Private Structured Text Generation
Shuai-Qi Wang, Vikas Raunak, A. Backurs, Victor Reis +6 more
2025Neural Information Processing Systems13 citations
Semantic Scholar
Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
A. Backurs, Krzysztof Onak
2016ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems13 citations
Semantic Scholar
On the Sum of L1 Influences
A. Backurs, Mohammad Bavarian
2013Cybersecurity and Cyberforensics Conference13 citations Open access
Semantic Scholar
Faster Kernel Matrix Algebra via Density Estimation
A. Backurs, P. Indyk, Cameron Musco, Tal Wagner
2021International Conference on Machine Learning12 citations
Semantic Scholar
Efficiently Computing Similarities to Private Datasets
A. Backurs, Zinan Lin, S. Mahabadi, Sandeep Silwal +1 more
2024International Conference on Learning Representations11 citations
Semantic Scholar
Data-to-text Generation by Splicing Together Nearest Neighbors
Sam Wiseman, A. Backurs, K. Stratos
2021Conference on Empirical Methods in Natural Language Processing10 citations Open access
Semantic Scholar
Better embeddings for planar Earth-Mover Distance over sparse sets
A. Backurs, P. Indyk
2014International Symposium on Computational Geometry10 citations Open access
Semantic Scholar
UvA-DARE (Digital Academic Repository) Optimal quantum query bounds for almost all Boolean functions
A. Ambainis, A. Backurs, Juris Smotrovs, R. de Wolf
9 citations
Semantic Scholar
Differentially Private Synthetic Data via APIs 4: Tabular Data
Toan Tran, A. Backurs, Zinan Lin, Victor Reis +2 more
2026arXiv.org6 citations
Semantic Scholar
DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
Jerry Chee, A. Backurs, R. Heck, Li Zhang +3 more
2025Annual Conference Computational Learning Theory6 citations
Semantic Scholar
On the sum of L 1 influences
A. Backurs, Mohammad Bavarian
20136 citations
Semantic Scholar
Active Local Learning
A. Backurs, Avrim Blum, Neha Gupta
2020Annual Conference Computational Learning Theory3 citations
Semantic Scholar
Generating (Formulaic) Text by Splicing Together Nearest Neighbors
Sam Wiseman, A. Backurs, K. Stratos
2021arXiv.org1 citations
Semantic Scholar
Two-Sided Kirszbraun Theorem
A. Backurs, S. Mahabadi, K. Makarychev, Y. Makarychev
2021International Symposium on Computational Geometry1 citations
Semantic Scholar
A note on more eﬃcient architectures for NLP
A. Backurs, Mingda Chen, Kevin Gimpel
20211 citations
Semantic Scholar
D S ] 3 M ar 2 01 6 Tight Hardness Results for Maximum Weight Rectangles
A. Backurs, Nishanth Dikkala, Christos Tzamos
20181 citations
Semantic Scholar
Influences in low-degree polynomials
A. Backurs
20121 citations
Semantic Scholar
Worst Case Analysis of Non-local Games
A. Ambainis, A. Backurs, K. Balodis, Agnis Skuskovniks +2 more
2011Conference on Current Trends in Theory and Practice of Informatics1 citations
Semantic Scholar