Arturs Backurs

According to our database, Arturs Backurs authored at least 48 papers between 2011 and 2024.

Collaborative distances:

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

2024

Efficiently Computing Similarities to Private Datasets.

Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, Jakub Tarnawski

CoRR, 2024

Differentially Private Synthetic Data via Foundation Model APIs 2: Text.

Chulin Xie, Zinan Lin, Arturs Backurs, Sivakanth Gopi, Da Yu, Huseyin A. Inan, Harsha Nori, Haotian Jiang, Huishuai Zhang, Yin Tat Lee, Bo Li, Sergey Yekhanin

CoRR, 2024

2023

Privately Aligning Language Models with Reinforcement Learning.

Fan Wu, Huseyin A. Inan, Arturs Backurs, Varun Chandrasekaran, Janardhan Kulkarni, Robert Sim

CoRR, 2023

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

Proceedings of the Eleventh International Conference on Learning Representations, 2023

2022

Unveiling Transformers with LEGO: a synthetic reasoning task.

Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, Tal Wagner

CoRR, 2022

Differentially Private Model Compression.

Fatemehsadat Mireshghallah, Arturs Backurs, Huseyin A. Inan, Lukas Wutschitz, Janardhan Kulkarni

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Differentially Private Fine-tuning of Language Models.

Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, Huishuai Zhang

Proceedings of the Tenth International Conference on Learning Representations, 2022

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

Generating (Formulaic) Text by Splicing Together Nearest Neighbors.

Sam Wiseman, Arturs Backurs, Karl Stratos

CoRR, 2021

Fast and Simple Modular Subset Sum.

Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Faster Kernel Matrix Algebra via Density Estimation.

Arturs Backurs, Piotr Indyk, Cameron Musco, Tal Wagner

Proceedings of the 38th International Conference on Machine Learning, 2021

Data-to-text Generation by Splicing Together Nearest Neighbors.

Sam Wiseman, Arturs Backurs, Karl Stratos

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, 2021

Two-Sided Kirszbraun Theorem.

Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Submodular Clustering in Low Dimensions.

Arturs Backurs, Sariel Har-Peled

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Impossibility Results for Grammar-Compressed Linear Algebra.

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 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

Active Local Learning.

Arturs Backurs, Avrim Blum, Neha Gupta

Proceedings of the Conference on Learning Theory, 2020

2019

Fast Modular Subset Sum using Linear Sketching.

Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, Hongxun Wu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Space and Time Efficient Kernel Density Estimation in High Dimensions.

Arturs Backurs, Piotr Indyk, Tal Wagner

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

Scalable Fair Clustering.

Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner

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

2018

Below P vs NP: fine-grained hardness for big data problems.

Arturs Backurs

PhD thesis, 2018

Subtree Isomorphism Revisited.

Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir

ACM Trans. Algorithms, 2018

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False).

Arturs Backurs, Piotr Indyk

SIAM J. Comput., 2018

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser.

Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams

SIAM J. Comput., 2018

Fast Modular Subset Sum using Linear Sketching.

Kyriakos Axiotis, Arturs Backurs, Christos Tzamos

CoRR, 2018

Towards tight approximation bounds for graph diameter and eccentricities.

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein

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

Efficient Density Evaluation for Smooth Kernels.

Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis

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

2017

Better Approximations for Tree Sparsity in Nearly-Linear Time.

Arturs Backurs, Piotr Indyk, Ludwig Schmidt

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

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks.

Arturs Backurs, Piotr Indyk, Ludwig Schmidt

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

Towards Hardness of Approximation for Polynomial Time Problems.

Amir Abboud, Arturs Backurs

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms.

Arturs Backurs, Christos Tzamos

Proceedings of the 34th International Conference on Machine Learning, 2017

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

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

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors.

Arturs Backurs, Krzysztof Onak

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

Tight Hardness Results for Maximum Weight Rectangles.

Arturs Backurs, Nishanth Dikkala, Christos Tzamos

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Which Regular Expression Patterns Are Hard to Match?

Arturs Backurs, Piotr Indyk

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces.

Arturs Backurs, Anastasios Sidiropoulos

Proceedings of the Approximation, 2016

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

Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.

Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams

CoRR, 2015

Tight Hardness Results for LCS and Other Sequence Similarity Measures.

Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Better embeddings for planar Earth-Mover Distance over sparse sets.

Arturs Backurs, Piotr Indyk

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

On the sum of L1 influences.

Arturs Backurs, Mohammad Bavarian

Electron. Colloquium Comput. Complex., 2013

Optimal quantum query bounds for almost all Boolean functions.

Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Worst Case Analysis of Non-local Games.

Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza

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

2012

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification.

Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh

Proceedings of the Theory of Quantum Computation, 2012

Grover's Algorithm with Errors.

Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Alexander Rivosh

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

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

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

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