49 citations · 193 across the 39 of their papers we have counts for
3 papers · 2 filters
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams +1
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk…
If the Current Clique Algorithms are Optimal, so is Valiant's Parser
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
The CFG recognition problem is: given a context-free grammar and a string of length , decide if can be obtained from . This is the most basic…
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for tw…