We have got 2 papers with coauthors from Helsinki in SODA 2025:

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture · A. Björklund, R. Curticapean, T. Husfeldt, P. Kaski, K. Pratt

We show that under the asymptotic rank conjecture, the chromatic number of an n-vertex graph can be computed deterministically in O(1.99982ⁿ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the O(2ⁿ poly(n)) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009].

On the Locality of Hall's Theorem · S. Brandt, Y. Maus, A. Narayanan, F. Schlager, J. Uitto

We introduce a local variant of Hall's theorem and use it to design asymptotically optimal algorithms for central graph problems such as edge-coloring.

And we have also got 3 papers in SOSA 2025:

A Multilinear Johnson–Lindenstrauss Transform · P. Kaski, H. Mannila, A. Matakos

The Johnson–Lindenstrauss family of transforms constitutes a key algorithmic tool for reducing the dimensionality of a Euclidean space with low distortion of distances. Rephrased from geometry to linear algebra, one seeks to reduce the dimension of a vector space while approximately preserving inner products. We present a multilinear generalization of this bilinear (inner product) setting that admits both an elementary randomized algorithm as well as a short proof of correctness using Orlicz quasinorms.

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths · N. Fischer, B. Haeupler, R. Latypov, A. Roeyskoe, A. Sulser

We design the first parallel algorithm with near-linear work and state-of-the-art span for the Single-Source Shortest Paths (SSSP) problem with negative-weight edges.

Simple approximation algorithms for Polyamorous Scheduling · Y. Biktairov, L. Gąsieniec, W. Po Jiamjitrak, Namrata, B. Smith, S. Wild

In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time between consecutive occurrences of the same edge. We improved the approximation ratio of this NP-hard problem using simple algorithms.