49 citations · 193 across the 39 of their papers we have counts for
3 papers · 2 filters
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast time algorithms for . On the other hand, the matrix product w…
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). This paper defines new versions of OV, $k…
Monochromatic Triangles, Triangle Listing and APSP
Virginia Vassilevska Williams, Yinzhan Xu
One of the main hypotheses in fine-grained complexity is that All-Pairs Shortest Paths (APSP) for -node graphs requires time. Another famous hypothesis is that the…