49 citations · 193 across the 39 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
quant-ph2014★ 4 cited
Quantum algorithms for shortest paths problems in structured instances
Aran Nayebi, Virginia Vassilevska Williams
We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path pr…
cs.DS2014★ 43 cited
Popular conjectures imply strong lower bounds for dynamic problems
Amir Abboud, Virginia Vassilevska Williams
We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in t…