I am a graduate student in the Theory of Computation group at MIT.
My advisor is Piotr Indyk.
E-mail: backurs ατ mit.edu
- "Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms" (with Christos Tzamos), Manuscript.
- "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.
- "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.