º£½ÇÉçÇø

An Algorithmic Polynomial Freiman–Ruzsa Theorem

Davi De Castro Silva, University of º£½ÇÉçÇø
Monday, 9 November 2026, 14:00–15:00, CS1.01

The Polynomial Freiman–Ruzsa (PFR) theorem, proved by Gowers, Green, Manners, and Tao in 2023, establishes a fundamental connection between combinatorial and algebraic notions of approximate structure. The theorem has far-reaching implications across combinatorics and theoretical computer science.

In this talk, I will introduce the context and motivation behind the PFR theorem, before presenting recent joint work with Jop Briët, Srinivasan Arunachalam, Arkopal Dutt, and Tom Gur, in which we develop efficient algorithms for several equivalent formulations of the theorem. A central theme of our work is the emergence of new connections between additive combinatorics, symplectic geometry, and quantum computation, which play a key role in our algorithmic results.

Based on the preprint .

Faster Algorithms for Minimum Degree Spanning Tree

, University of º£½ÇÉçÇø
Monday, 16 November 2026, 14:00–15:00, CS1.01

The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established in the early 1990s: Furer and Raghavachari [FR92] gave an ~O(mn)-time algorithm that computes a spanning tree with maximum degree ∆*+1, where ∆* denotes the optimum value. It remains wide open as to whether similarly strong guarantees can be achieved by algorithms with faster runtimes.

We make substantial progress towards this question by obtaining: (i) an mn^{1/2+o(1)} time algorithm that computes a spanning tree with maximum degree ∆*+1, and (ii) an ~O(m/ε^3) time algorithm that computes a spanning tree with maximum degree ⌈(1+ ε)∆*⌉ + 1. Both our algorithms are deterministic.

This is a joint work with Sayan Bhattacharya, Thatchaphol Saranurak, and Haoze Wang.

Adaptive Fully Dynamic k-Center Clustering with (Near-)Optimal Worst-Case Guarantees

, University of º£½ÇÉçÇø
Monday, 23 November 2026, 14:00–15:00, CS1.01

The k-center problem is a fundamental clustering problem that asks us to choose k centers to minimize the maximum distance of any point to its nearest center. In real-world applications, points are continuously inserted and deleted. Ideally, we would like to maintain a good solution while processing each update quickly and changing as few centers as possible.

In this talk, I will present a dynamic algorithm that achieves all three goals simultaneously: a constant-factor approximation, near-optimal worst-case update time, and constant worst-case recourse, even against an adaptive adversary. Interestingly, we will see that these guarantees are essentially the best possible, up to polylogarithmic factors.

This is joint work with Mara Grilnberger and will appear in the proceedings of SODA 2027.

arXiv: