23 citations · 23 across the 3 of their papers we have counts for
3 papers
cs.DS2023
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…
cs.DS2016
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Greg Bodwin, Seth Pettie
Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say …
cs.CC2015★ 23 cited
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…