Connecting Computational Models Through Combinatorial StructureLecture

by Dr Peter Kiss

Tuesday Nov 3, 2026, 9:30 AM → 10:15 AM Europe/Berlin

Endenicher Allee 60/1-016 - Lipschitzsaal (Mathezentrum)

Techniques developed for one computational model can reveal new ways to approach a problem in another. The talk will explore this interplay through dynamic graph matching and its connections to sublinear algorithms, streaming computation, and extremal combinatorics.

The main focus will be recent frameworks for dynamic matching, whose update times are governed by the density of Ruzsa–Szemerédi graphs. The talk explores how these frameworks combine sublinear algorithmic techniques with combinatorial structure to obtain improved dynamic algorithms. These connections suggest a broader research direction: identifying the structures that govern algorithmic complexity and using them to transfer insights between computational models.