49 citations · 193 across the 39 of their papers we have counts for
7 papers · 2 filters
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu +2
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we a…
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Andrea Lincoln, Virginia Vassilevska Williams, Ryan Williams
Fine-grained reductions have established equivalences between many core problems with -time algorithms on -node weighted graphs, such as Shortest Cycle, All-Pair…
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
Greg Bodwin, Michael Dinitz, Merav Parter +1
A -spanner of a graph is a sparse subgraph whose shortest path distances match those of up to a multiplicative error . In this paper we study spanners that are re…
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Karl Bringmann, Fabrizio Grandoni, Barna Saha +1
It is a major open problem whether the -product of two matrices has a truly sub-cubic (i.e. for ) time algorithm, in particular since it is…
Dynamic Parameterized Problems and Algorithms
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
Fixed-parameter algorithms and kernelization are two powerful methods to solve -hard problems. Yet, so far those algorithms have been largely restricted to static inpu…
Preserving Distances in Very Faulty Graphs
Greg Bodwin, Fabrizio Grandoni, Merav Parter +1
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, res…