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

- "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.