Edit distance cannot be computed in strongly subquadratic time (unless SETH is false) A Backurs, P Indyk Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015 | 272 | 2015 |

Tight hardness results for LCS and other sequence similarity measures A Abboud, A Backurs, VV Williams 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 59-78, 2015 | 185* | 2015 |

If the current clique algorithms are optimal, so is Valiant's parser A Abboud, A Backurs, VV Williams SIAM Journal on Computing 47 (6), 2527-2555, 2018 | 69 | 2018 |

Which regular expression patterns are hard to match? A Backurs, P Indyk 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016 | 57 | 2016 |

Scalable fair clustering A Backurs, P Indyk, K Onak, B Schieber, A Vakilian, T Wagner arXiv preprint arXiv:1902.03519, 2019 | 48 | 2019 |

Towards tight approximation bounds for graph diameter and eccentricities A Backurs, L Roditty, G Segal, VV Williams, N Wein Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018 | 36 | 2018 |

Subtree isomorphism revisited A Abboud, A Backurs, TD Hansen, V Vassilevska Williams, O Zamir ACM Transactions on Algorithms (TALG) 14 (3), 1-23, 2018 | 30 | 2018 |

Improving viterbi is hard: Better runtimes imply faster clique algorithms A Backurs, C Tzamos International Conference on Machine Learning, 311-321, 2017 | 30 | 2017 |

Tight hardness results for maximum weight rectangles A Backurs, N Dikkala, C Tzamos arXiv preprint arXiv:1602.05837, 2016 | 26 | 2016 |

Towards hardness of approximation for polynomial time problems A Abboud, A Backurs 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 2017 | 23 | 2017 |

Search by quantum walks on two-dimensional grid without amplitude amplification A Ambainis, A Bačkurs, N Nahimovs, R Ozols, A Rivosh Conference on Quantum Computation, Communication, and Cryptography, 87-97, 2012 | 23 | 2012 |

Better approximations for tree sparsity in nearly-linear time A Backurs, P Indyk, L Schmidt Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017 | 21 | 2017 |

On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks A Backurs, P Indyk, L Schmidt Advances in Neural Information Processing Systems, 4308-4318, 2017 | 21 | 2017 |

Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve A Abboud, A Backurs, K Bringmann, M Künnemann 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017 | 20 | 2017 |

Search by quantum walks on two-dimensional grid without amplitude amplification A Ambainis, A Backurs, N Nahimovs, R Ozols, A Rivosh arXiv preprint arXiv:1112.3337, 2011 | 13 | 2011 |

Nearly-optimal bounds for sparse recovery in generic norms, with applications to *k*-median sketchingA Backurs, P Indyk, I Razenshteyn, DP Woodruffs Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete …, 2016 | 12 | 2016 |

Quantum strategies are better than classical in almost any XOR game A Ambainis, A Bačkurs, K Balodis, D Kravčenko, R Ozols, J Smotrovs, ... International Colloquium on Automata, Languages, and Programming, 25-37, 2012 | 12 | 2012 |

Fast modular subset sum using linear sketching K Axiotis, A Backurs, C Jin, C Tzamos, H Wu Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019 | 10 | 2019 |

Efficient density evaluation for smooth kernels A Backurs, M Charikar, P Indyk, P Siminelakis 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS …, 2018 | 7 | 2018 |

Space and Time Efficient Kernel Density Estimation in High Dimensions A Backurs, P Indyk, T Wagner Advances in Neural Information Processing Systems, 15799-15808, 2019 | 6 | 2019 |