The Taub Faculty of Computer Science Events and Talks

We consider the problem of approximate counting of triangles and longer fixed length cycles in undirected and directed graphs. We provide an algorithm which is faster as t, the number of copies of the searched subgraph, increases. Our running time, which significantly improves upon the state of the art (Tětek [ICALP’22]), is the same as that of multiplying an n x (n/t) matrix by an (n/t) x n matrix, up to polylogarithmic factors. Finally, we show that under popular fine-grained hypotheses, this running time is optimal. The talk is based on a joint work with Keren Censor-Hillel and Virginia Vassilevska Williams. To appear in ICALP 2024.