Detecting a k-clique in a graph, for k at least 3, is a fundamental problem in fine-grained complexity, conjectured to require n^(omega * k / 3 - o(1)) time, where omega is the matrix multiplication exponent. In this talk, we present new detection and approximate counting algorithms for graphs containing many k-cliques.
The talk is based on a joint work with Keren Censor-Hillel and Virginia Vassilevska Williams. To appear in STOC 2025.