31 citations · 35 across the 22 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
The SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been abo…
cs.CC2022
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin, Yinzhan Xu
The main theme of this paper is using -dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vect…
cs.CC2020
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…