YRF 2026: Jukka Suomela - A problem that has kept me entertained for nearly twenty years

Young Researchers Forum 2026 (https://sites.google.com/view/youngre...) Speaker: Jukka Suomela Talk Title: A problem that has kept me entertained for nearly twenty years Abstract: I think it was around 2008 when I started to get obsessed with a seemingly trivial problem: finding a maximal matching in 2-colored graphs. Back then we needed it as a subroutine for finding vertex covers. There is a trivial "proposal algorithm" where black nodes send proposals one by one to their white neighbors and white nodes accept the first proposal that they get. In graphs of maximum degree Δ this is O(Δ) rounds. Can we do better? Around 2011 we figured out that the answer is "sort of no". Around 2014 I gave a talk at ADGA where I tried to get everyone else excited about this question, with little success. Only in late 2018 did we finally prove that the answer is a really solid "no", and this led to a Best Paper Award at FOCS 2019. And in 2026 this problem still keeps giving, in unexpected contexts, such as quantum computing. In this talk I will discuss this journey with a single problem that has lasted for at least 18 years so far.