Arturs Backurs

I am a graduate student in the Theory of Computation group at MIT.

My advisor is Piotr Indyk.

E-mail: backurs ατ mit.edu

Office: 32-G628

Papers

• "On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks" (with Piotr Indyk and Ludwig Schmidt), Manuscript.
  
  
• "Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms" (with Christos Tzamos), ICML, 2017.
  
  
• "Better Approximations for Tree Sparsity in Nearly Linear Time" (with Piotr Indyk and Ludwig Schmidt), SODA, 2017.
  
  
• "Towards Hardness of Approximation for Polynomial Time Problems" (with Amir Abboud), ITCS, 2017. Co-winner of Best Student Paper Award.
  
  
• "Which Regular Expression Patterns are Hard to Match?" (with Piotr Indyk), FOCS, 2016.
  
  
• "Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces" (with Anastasios Sidiropoulos), APPROX, 2016.
  
  
• "Tight Hardness Results for Maximum Weight Rectangles" (with Nishanth Dikkala and Christos Tzamos), ICALP, 2016.
  
  
• "Fast Algorithms for Parsing Sequences of Parentheses with Few Errors" (with Krzysztof Onak), PODS, 2016.
  
  
• "Subtree Isomorphism Revisited" (with Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams and Or Zamir), SODA, 2016.
  
  
• "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), SODA, 2016.
  
  
• "If the Current Clique Algorithms are Optimal, So is Valiant's Parser" (with Amir Abboud and Virginia Vassilevska Williams), FOCS, 2015.
  
  
• "Tight Hardness Results for LCS and Other Sequence Similarity Measures" (with Amir Abboud and Virginia Vassilevska Williams), FOCS, 2015.
  
  
• "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)" (with Piotr Indyk), STOC, 2015 and HALG, 2016.
  
  
• "Better embeddings for planar Earth-Mover Distance over sparse sets" (with Piotr Indyk), SoCG, 2014.
  
  
• "On the sum of L1 influences" (with Mohammad Bavarian), CCC, 2014.
  
  
• "Worst Case Analysis of Non-local Games" (with Andris Ambainis, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs and Madars Virza), SOFSEM, 2013.
  
  
• "Optimal quantum query bounds for almost all Boolean functions" (with Andris Ambainis, Juris Smotrovs and Ronald de Wolf), 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), ICALP, 2012.
  
  
• "Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification" (with Andris Ambainis, Nikolajs Nahimovs, Raitis Ozols and Alexander Rivosh), TQC, 2012.
  
  
• "Grover's Algorithm with Errors" (with Andris Ambainis, Nikolajs Nahimovs and Alexander Rivosh), MEMICS, 2012.