Join us this π-day (14 March) for a celebration of the mathematics we learn, apply, and develop at ITU. The event will consist of a talk by Thore Husfeldt followed by pie and coffee.

We ask participants to please register before March 11 in order to get an estimate of the amount of pie needed.

Speaker: Thore Husfeldt

Title: The shortest even cycle problem is tractable

Abstract: We’ve known since the early days of algorithms how to finding a short cycle in an undirected graph quickly, arguably a problem (about navigating mazes) already considered and solved by the ancients. This problem varies in complexity dramatically as soon as we specify the length of the cycle: a shortest cycle of odd length (3, 5, 7, ...) is easily found (I’ll show you), but nobody knew how to find a shortest cycle of even length (2, 4, 6, ...) quickly. In fact, this problem (the Even Shortest Cycle Problem) was not known to admit a polynomial-time algorithm. I will sketch the intellectual history of this problem and show how we solved it. Relevant for π Day, the solution uses tools from various branches of mathematics other than combinatorics, including probability theory, linear algebra, and algebraic number theory. I’ll try to explain what these connections are; the talk is aimed at an audience with very little background in those areas. The talk contains attractive animations from https://youtu.be/4wY1GRTxF84 that I’m pretty proud of.

Andreas Björklund, Thore Husfeldt, Petteri Kaski: The Shortest Even Cycle Problem Is Tractable. Symposium on the Theory of Computing (STOC) 2022. SIAM Journal of Computing special issue for STOC, to appear.

Organisers: Maaike Zwart and Rasmus Møgelberg (Theoretical Computer Science)