Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Fast Approximate Counting of Cycles
event speaker icon
Tomer Even (Technion)
event date icon
Wednesday, 26.06.2024, 13:00
event location icon
Amado 719
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.