13 citations · 17 across the 5 of their papers we have counts for
3 papers · 1 filter
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…
Conditional Hardness for Sensitivity Problems
Monika Henzinger, Andrea Lincoln, Stefan Neumann +1
In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allow…