Arturs Backurs

79 papers A* 29A 3B 1Journal 37Unranked 8

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory. COLT Jerry Chee, Arturs Backurs, Rainie Heck, Li Zhang, Janardhan Kulkarni, Thomas Rothvoss, Sivakanth Gopi
2025	J	`jnl`	DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory. CoRR Jerry Chee, Arturs Backurs, Rainie Heck, Li Zhang, Janardhan Kulkarni, Thomas Rothvoss, Sivakanth Gopi
2025	J	`jnl`	Struct-Bench: A Benchmark for Differentially Private Structured Text Generation. CoRR Shuaiqi Wang, Vikas Raunak, Arturs Backurs, Victor Reis, Pei Zhou, Sihao Chen, Longqi Yang, Zinan Lin, Sergey Yekhanin, Giulia Fanti
2024	J	`jnl`	Differentially Private Fine-tuning of Language Models. J. Priv. Confidentiality 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
2024	A*	`conf`	Differentially Private Synthetic Data via Foundation Model APIs 2: Text. ICML 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
2024	J	`jnl`	Differentially Private Synthetic Data via Foundation Model APIs 2: Text. CoRR 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
2024	A*	`conf`	Efficiently Computing Similarities to Private Datasets. ICLR Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, Jakub Tarnawski
2024	J	`jnl`	Efficiently Computing Similarities to Private Datasets. CoRR Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, Jakub Tarnawski
2024	A*	`conf`	Privately Aligning Language Models with Reinforcement Learning. ICLR Fan Wu, Huseyin A. Inan, Arturs Backurs, Varun Chandrasekaran, Janardhan Kulkarni, Robert Sim
2023	A*	`conf`	Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping. ICLR Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, Jiang Bian
2023	J	`jnl`	Privately Aligning Language Models with Reinforcement Learning. CoRR Fan Wu, Huseyin A. Inan, Arturs Backurs, Varun Chandrasekaran, Janardhan Kulkarni, Robert Sim
2022	A*	`conf`	Differentially Private Fine-tuning of Language Models. ICLR 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
2022	A*	`conf`	Differentially Private Model Compression. NeurIPS Fatemehsadat Mireshghallah, Arturs Backurs, Huseyin A. Inan, Lukas Wutschitz, Janardhan Kulkarni
2022	J	`jnl`	Differentially Private Model Compression. CoRR Fatemehsadat Mireshghallah, Arturs Backurs, Huseyin A. Inan, Lukas Wutschitz, Janardhan Kulkarni
2022	J	`jnl`	Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping. CoRR Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, Jiang Bian
2022	J	`jnl`	Unveiling Transformers with LEGO: a synthetic reasoning task. CoRR Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, Tal Wagner
2021	—	`conf`	Data-to-text Generation by Splicing Together Nearest Neighbors. EMNLP (1) Sam Wiseman, Arturs Backurs, Karl Stratos
2021	J	`jnl`	Differentially Private Fine-tuning of Language Models. CoRR 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
2021	—	`conf`	Fast and Simple Modular Subset Sum. SOSA Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
2021	A*	`conf`	Faster Kernel Matrix Algebra via Density Estimation. ICML Arturs Backurs, Piotr Indyk, Cameron Musco, Tal Wagner
2021	J	`jnl`	Faster Kernel Matrix Algebra via Density Estimation. CoRR Arturs Backurs, Piotr Indyk, Cameron Musco, Tal Wagner
2021	J	`jnl`	Generating (Formulaic) Text by Splicing Together Nearest Neighbors. CoRR Sam Wiseman, Arturs Backurs, Karl Stratos
2021	J	`jnl`	Toward Tight Approximation Bounds for Graph Diameter and Eccentricities. SIAM J. Comput. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein
2021	A*	`conf`	Two-Sided Kirszbraun Theorem. SoCG Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
2020	A*	`conf`	Active Local Learning. COLT Arturs Backurs, Avrim Blum, Neha Gupta
2020	J	`jnl`	Active Local Learning. CoRR Arturs Backurs, Avrim Blum, Neha Gupta
2020	J	`jnl`	Fast and Simple Modular Subset Sum. CoRR Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
2020	A*	`conf`	Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020	J	`jnl`	Impossibility Results for Grammar-Compressed Linear Algebra. CoRR Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020	A*	`conf`	Scalable Nearest Neighbor Search for Optimal Transport. ICML Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner
2020	—	`conf`	Submodular Clustering in Low Dimensions. SWAT Arturs Backurs, Sariel Har-Peled
2020	J	`jnl`	Submodular Clustering in Low Dimensions. CoRR Arturs Backurs, Sariel Har-Peled
2019	A*	`conf`	Fast Modular Subset Sum using Linear Sketching. SODA Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, Hongxun Wu
2019	A*	`conf`	Scalable Fair Clustering. ICML Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner
2019	J	`jnl`	Scalable Fair Clustering. CoRR Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner
2019	A*	`conf`	Space and Time Efficient Kernel Density Estimation in High Dimensions. NeurIPS Arturs Backurs, Piotr Indyk, Tal Wagner
2018	—	`—`	Below P vs NP: fine-grained hardness for big data problems. Arturs Backurs
2018	J	`jnl`	Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). SIAM J. Comput. Arturs Backurs, Piotr Indyk
2018	A*	`conf`	Efficient Density Evaluation for Smooth Kernels. FOCS Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis
2018	J	`jnl`	Fast Modular Subset Sum using Linear Sketching. CoRR Kyriakos Axiotis, Arturs Backurs, Christos Tzamos
2018	J	`jnl`	Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2018	J	`jnl`	If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. SIAM J. Comput. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2018	J	`jnl`	Subtree Isomorphism Revisited. ACM Trans. Algorithms Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
2018	J	`jnl`	Towards Tight Approximation Bounds for Graph Diameter and Eccentricities. CoRR Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein
2018	A*	`conf`	Towards tight approximation bounds for graph diameter and eccentricities. STOC Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein
2017	A*	`conf`	Better Approximations for Tree Sparsity in Nearly-Linear Time. SODA Arturs Backurs, Piotr Indyk, Ludwig Schmidt
2017	A*	`conf`	Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2017	A*	`conf`	Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms. ICML Arturs Backurs, Christos Tzamos
2017	—	`conf`	On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks. NIPS Arturs Backurs, Piotr Indyk, Ludwig Schmidt
2017	J	`jnl`	On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks. CoRR Arturs Backurs, Piotr Indyk, Ludwig Schmidt
2017	A	`conf`	Towards Hardness of Approximation for Polynomial Time Problems. ITCS Amir Abboud, Arturs Backurs
2016	—	`conf`	Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces. APPROX-RANDOM Arturs Backurs, Anastasios Sidiropoulos
2016	A*	`conf`	Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. PODS Arturs Backurs, Krzysztof Onak
2016	J	`jnl`	Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms. CoRR Arturs Backurs, Christos Tzamos
2016	A*	`conf`	Nearly-optimal bounds for sparse recovery in generic norms, with applications to SODA Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff
2016	A*	`conf`	Subtree Isomorphism Revisited. SODA Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
2016	A*	`conf`	Tight Hardness Results for Maximum Weight Rectangles. ICALP Arturs Backurs, Nishanth Dikkala, Christos Tzamos
2016	J	`jnl`	Tight Hardness Results for Maximum Weight Rectangles. CoRR Arturs Backurs, Nishanth Dikkala, Christos Tzamos
2016	A*	`conf`	Which Regular Expression Patterns Are Hard to Match? FOCS Arturs Backurs, Piotr Indyk
2015	A*	`conf`	Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC Arturs Backurs, Piotr Indyk
2015	A*	`conf`	If the Current Clique Algorithms are Optimal, So is Valiant's Parser. FOCS Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015	J	`jnl`	If the Current Clique Algorithms are Optimal, so is Valiant's Parser. CoRR Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015	J	`jnl`	Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching. CoRR Arturs Backurs, Piotr Indyk, Eric Price, Ilya P. Razenshteyn, David P. Woodruff
2015	J	`jnl`	Quadratic-Time Hardness of LCS and other Sequence Similarity Measures. CoRR Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015	J	`jnl`	Subtree Isomorphism Revisited. CoRR Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
2015	A*	`conf`	Tight Hardness Results for LCS and Other Sequence Similarity Measures. FOCS Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
2015	J	`jnl`	Which Regular Expression Patterns are Hard to Match? CoRR Arturs Backurs, Piotr Indyk
2014	A*	`conf`	Better embeddings for planar Earth-Mover Distance over sparse sets. SoCG Arturs Backurs, Piotr Indyk
2014	J	`jnl`	Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). CoRR Arturs Backurs, Piotr Indyk
2014	A	`conf`	On the Sum of L1 Influences. CCC Arturs Backurs, Mohammad Bavarian
2013	J	`jnl`	On the sum of $L1$ influences CoRR Arturs Backurs, Mohammad Bavarian
2013	J	`jnl`	On the sum of L1 influences. Electron. Colloquium Comput. Complex. Arturs Backurs, Mohammad Bavarian
2013	A	`conf`	Optimal quantum query bounds for almost all Boolean functions. STACS Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf
2013	B	`conf`	Worst Case Analysis of Non-local Games. SOFSEM Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza
2012	—	`conf`	Grover's Algorithm with Errors. MEMICS Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Alexander Rivosh
2012	—	`conf`	Quantum Strategies Are Better Than Classical in Almost Any XOR Game. ICALP (1) Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitrijs Kravcenko, Raitis Ozols, Juris Smotrovs, Madars Virza
2012	—	`conf`	Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. TQC Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh
2011	J	`jnl`	Quantum strategies are better than classical in almost any XOR game CoRR Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitry Kravchenko, Raitis Ozols, Juris Smotrovs, Madars Virza
2011	J	`jnl`	Search by quantum walks on two-dimensional grid without amplitude amplification CoRR Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh