49 citations · 193 across the 39 of their papers we have counts for
Showing 2022 · cs.CCShow all
2 papers · 2 filters
cs.CC2022
Induced Cycles and Paths Are Harder Than You Think
Mina Dalirrooyfard, Virginia Vassilevska Williams
The goal of the paper is to give fine-grained hardness results for the Subgraph Isomorphism (SI) problem for fixed size induced patterns , based on the -Clique hypothesis tha…
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…