Theory Seminar, Wednesday Nov 19: Tomer Even (Technion) - Faster k-Clique Detection in Graphs with Many k-Cliques

[Arnold Filtser]

Hi all,

Next week (Wed Nov 19, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker:  Tomer Even (Technion)
Title: Faster k-Clique Detection in Graphs with Many k-Cliques
Abstract:   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 joint work with Keren Censor-Hillel and Virginia Vassilevska Williams (ICALP 2025; STOC 2025).