10 citations · 14 across the 10 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Beating Trivial Time for Tricky Triangle Tasks
Neha Pant, Ryan Williams
For several well-studied triangle detection problems in the literature, the trivial enumeration algorithms are known to be optimal (up to the exponent) assuming popular fine-graine…
cs.DS2017
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…
cs.DS2016
Deterministic Time-Space Tradeoffs for k-SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang +1
Given a set of numbers, the -SUM problem asks for a subset of numbers that sums to zero. When the numbers are integers, the time and space complexity of -SUM is generally…