Quantum strategies are better than classical in almost any XOR game - Andris Ambainis; Arturs Backurs; Kaspars Balodis; Dmitry Kravchenko; Raitis Ozols; Juris Smotrovs; Madars Virza (CoRR, 2011)

Quantum Strategies Are Better Than Classical in Almost Any XOR Game. - Andris Ambainis; Arturs Backurs; Kaspars Balodis; Dmitrijs Kravcenko; Raitis Ozols; Juris Smotrovs; Madars Virza (ICALP (1), 2012)

Grover's Algorithm with Errors. - Andris Ambainis; Arturs Backurs; Nikolajs Nahimovs; Alexander Rivosh (MEMICS, 2012)

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. - Andris Ambainis; Arturs Backurs; Nikolajs Nahimovs; Raitis Ozols; Alexander Rivosh (TQC, 2012)

Worst Case Analysis of Non-local Games. - Andris Ambainis; Arturs Backurs; Kaspars Balodis; Agnis Skuskovniks; Juris Smotrovs; Madars Virza (SOFSEM, 2013)

Optimal quantum query bounds for almost all Boolean functions. - Andris Ambainis; Arturs Backurs; Juris Smotrovs; Ronald de Wolf (STACS, 2013)

On the sum of L1 influences. - Arturs Backurs; Mohammad Bavarian (Electron. Colloquium Comput. Complex., 2013)

Better embeddings for planar Earth-Mover Distance over sparse sets. - Arturs Backurs; Piotr Indyk (SoCG, 2014)

Tight Hardness Results for LCS and Other Sequence Similarity Measures. - Amir Abboud; Arturs Backurs; Virginia Vassilevska Williams (FOCS, 2015)

Quadratic-Time Hardness of LCS and other Sequence Similarity Measures. - Amir Abboud; Arturs Backurs; Virginia Vassilevska Williams (CoRR, 2015)

Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching. - Arturs Backurs; Piotr Indyk; Eric Price 001; Ilya P. Razenshteyn; David P. Woodruff (CoRR, 2015)

Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces. - Arturs Backurs; Anastasios Sidiropoulos (APPROX-RANDOM, 2016)

Which Regular Expression Patterns Are Hard to Match? - Arturs Backurs; Piotr Indyk (FOCS, 2016)

Tight Hardness Results for Maximum Weight Rectangles. - Arturs Backurs; Nishanth Dikkala; Christos Tzamos (ICALP, 2016)

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. - Arturs Backurs; Krzysztof Onak (PODS, 2016)

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. - Arturs Backurs; Piotr Indyk; Ilya P. Razenshteyn; David P. Woodruff (SODA, 2016)

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. - Amir Abboud; Arturs Backurs; Karl Bringmann; Marvin Künnemann (FOCS, 2017)

Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms. - Arturs Backurs; Christos Tzamos (ICML, 2017)

Towards Hardness of Approximation for Polynomial Time Problems. - Amir Abboud; Arturs Backurs (ITCS, 2017)

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks. - Arturs Backurs; Piotr Indyk; Ludwig Schmidt (NIPS, 2017)

Better Approximations for Tree Sparsity in Nearly-Linear Time. - Arturs Backurs; Piotr Indyk; Ludwig Schmidt (SODA, 2017)

Efficient Density Evaluation for Smooth Kernels. - Arturs Backurs; Moses Charikar; Piotr Indyk; Paris Siminelakis (FOCS, 2018)

Towards tight approximation bounds for graph diameter and eccentricities. - Arturs Backurs; Liam Roditty; Gilad Segal; Virginia Vassilevska Williams; Nicole Wein (STOC, 2018)

Fast Modular Subset Sum using Linear Sketching. - Kyriakos Axiotis; Arturs Backurs; Christos Tzamos (CoRR, 2018)

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. - Amir Abboud; Arturs Backurs; Virginia Vassilevska Williams (SIAM J. Comput., 2018)

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). - Arturs Backurs; Piotr Indyk (SIAM J. Comput., 2018)

Subtree Isomorphism Revisited. - Amir Abboud; Arturs Backurs; Thomas Dueholm Hansen; Virginia Vassilevska Williams; Or Zamir (ACM Trans. Algorithms, 2018)

Below P vs NP: fine-grained hardness for big data problems. - Arturs Backurs (2018)

Scalable Fair Clustering. - Arturs Backurs; Piotr Indyk; Krzysztof Onak; Baruch Schieber; Ali Vakilian; Tal Wagner (ICML, 2019)

Space and Time Efficient Kernel Density Estimation in High Dimensions. - Arturs Backurs; Piotr Indyk; Tal Wagner (NeurIPS, 2019)

Fast Modular Subset Sum using Linear Sketching. - Kyriakos Axiotis; Arturs Backurs; Ce Jin 001; Christos Tzamos; Hongxun Wu (SODA, 2019)

Active Local Learning. - Arturs Backurs; Avrim Blum; Neha Gupta 002 (COLT, 2020)

Scalable Nearest Neighbor Search for Optimal Transport. - Arturs Backurs; Yihe Dong; Piotr Indyk; Ilya P. Razenshteyn; Tal Wagner (ICML, 2020)

Impossibility Results for Grammar-Compressed Linear Algebra. - Amir Abboud; Arturs Backurs; Karl Bringmann; Marvin Künnemann (NeurIPS, 2020)

Submodular Clustering in Low Dimensions. - Arturs Backurs; Sariel Har-Peled (SWAT, 2020)

Two-Sided Kirszbraun Theorem. - Arturs Backurs; Sepideh Mahabadi; Konstantin Makarychev; Yury Makarychev (SoCG, 2021)

Data-to-text Generation by Splicing Together Nearest Neighbors. - Sam Wiseman; Arturs Backurs; Karl Stratos (EMNLP (1), 2021)

Faster Kernel Matrix Algebra via Density Estimation. - Arturs Backurs; Piotr Indyk; Cameron Musco; Tal Wagner (ICML, 2021)

Fast and Simple Modular Subset Sum. - Kyriakos Axiotis; Arturs Backurs; Karl Bringmann; Ce Jin 001; Vasileios Nakos; Christos Tzamos; Hongxun Wu (SOSA, 2021)

Generating (Formulaic) Text by Splicing Together Nearest Neighbors. - Sam Wiseman; Arturs Backurs; Karl Stratos (CoRR, 2021)

Toward Tight Approximation Bounds for Graph Diameter and Eccentricities. - Arturs Backurs; Liam Roditty; Gilad Segal; Virginia Vassilevska Williams; Nicole Wein (SIAM J. Comput., 2021)

Differentially Private Model Compression. - Fatemehsadat Mireshghallah; Arturs Backurs; Huseyin A. Inan; Lukas Wutschitz; Janardhan Kulkarni (NeurIPS, 2022)

Unveiling Transformers with LEGO: a synthetic reasoning task. - Yi Zhang; Arturs Backurs; Sébastien Bubeck; Ronen Eldan; Suriya Gunasekar; Tal Wagner (CoRR, 2022)

Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping. - Jiyan He; Xuechen Li; Da Yu; Huishuai Zhang; Janardhan Kulkarni; Yin Tat Lee; Arturs Backurs; Nenghai Yu; Jiang Bian 002 (ICLR, 2023)

Efficiently Computing Similarities to Private Datasets. - Arturs Backurs; Zinan Lin 001; Sepideh Mahabadi; Sandeep Silwal; Jakub Tarnawski (ICLR, 2024)

Privately Aligning Language Models with Reinforcement Learning. - Fan Wu; Huseyin A. Inan; Arturs Backurs; Varun Chandrasekaran; Janardhan Kulkarni; Robert Sim (ICLR, 2024)

Differentially Private Synthetic Data via Foundation Model APIs 2: Text. - Chulin Xie; Zinan Lin 001; Arturs Backurs; Sivakanth Gopi; Da Yu; Huseyin A. Inan; Harsha Nori; Haotian Jiang; Huishuai Zhang; Yin Tat Lee; Bo Li 026; Sergey Yekhanin (ICML, 2024)

Differentially Private Fine-tuning of Language Models. - Da Yu; Saurabh Naik; Arturs Backurs; Sivakanth Gopi; Huseyin A. Inan; Gautam Kamath 001; Janardhan Kulkarni; Yin Tat Lee; Andre Manoel; Lukas Wutschitz; Sergey Yekhanin; Huishuai Zhang (J. Priv. Confidentiality, 2024)

DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory. - Jerry Chee; Arturs Backurs; Rainie Heck; Li Zhang; Janardhan Kulkarni; Thomas Rothvoss; Sivakanth Gopi (COLT, 2025)