Schedule and Abstracts

Friday May 22

8:55-9:00 Welcome remarks

9:00-9:30 Guillaume Ducoffe. Title: Solving the weighted center problem fast

Abstract: For every weight assignment pi to the vertices in a graph G, the radius function r_pi maps every vertex of G to its largest weighted distance to the other vertices. The weighted center problem asks to find a vertex of G that minimizes the radius function r_pi. The classic center problem corresponds to the case where pi(v) = 1 for every vertex v. In the literature, various almost linear-time algorithms, or at least truly subquadratic-time algorithms, have been proposed for the center problem on some well-structured classes of graphs. The question addressed during this talk will be whether we can design algorithms for the weighted center problem whose running times match the best ones known for the center problem. I will briefly present recent results in this direction. 

This is joint work with Jeremie Chalopin, Victor Chepoi, Feodor Dragan and Yann Vaxes.

9:30-10:00 Diana Ghinea. Title: Communication-Optimal Convex Agreement 

Abstract: Byzantine Agreement (BA) allows a set of n parties to agree on a value even when up to t of the parties involved are corrupted. While previous works have shown that, for L-bit inputs, BA can be achieved with the optimal communication complexity O(L n) for sufficiently large L, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications. This gave rise to the notion of Convex Agreement (CA), introduced by Vaidya and Garg [PODC'13], which requires the honest parties' outputs to be in the convex hull of the honest inputs. Unfortunately, all existing CA protocols incur a communication complexity of at least O(L n^2). In this work, we introduce the first synchronous CA protocol with optimal communication of O(L n) bits for L-bit integer inputs, given that L is sufficiently large.

10:00-10:30 Tamio-Vesa Nakajima. Title: Virtual Memory Powersort 

Abstract: We discuss a more space-efficient implementation of adaptive mergesort:

Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption of the algorithm; specifically, for sorting n objects the required buffer area is reduced from space for n/2 objects to O(sqrt(n log n)) objects. While this space-efficiency can be achieved (indeed reduced to O(1)) conceptually very easily with known inplace merging algorithms, using these as a drop-in replacement for the standard merge algorithm incurs a substantial slow-down. Virtual-Memory Powersort, by contrast, uses the same number of moves and comparisons as previous Powersort implementations up to an additive O(n) term. We report on an empirical running-time study comparing our implementation against other Powersort variants and state-of-the-art stable sorting methods, demonstrating that almost in-place stable sorting can be achieved with negligible overhead in many scenarios.

10:30-11:15 BREAK

11:15-11:45 Stefania Ionescu. Title: “I’m not good at this, so don’t match me”: accounting for strategic behavior in outcome-based matchings

Abstract: In two-sided matching markets such as school choice and refugee assignment, it is difficult to find the best matchings. To aid, data-driven decision support systems can (1) predict future outcomes based on historical data and (2) use this information to produce more efficient matchings. Although both are part of a complex socio-technical system, these prediction and matching mechanisms are usually analyzed separately. But what happens if we consider the market as a whole? In this talk, I present a new type of strategic behavior of agents targeting the prediction mechanism by leveraging the repeated nature of the market. This strategic behavior is not merely an attack on the reported data but a change in the actual interaction between agents. I will discuss when such strategies are optimal and what their consequences are (e.g., unfairness and inefficiencies). I will also discuss potential algorithmic solutions that can trade off between the utilities of different types of agents, preventing, by design, eventual discrimination induced by sensitive features of individuals.

11:45 - 12:15 Alex Popa. Title: A 9/5 Approximation Algorithm for the Maximum Edge 2-Coloring Problem on Bipartite Graphs

Abstract: An edge 2-coloring is a coloring of the edges of an undirected graph such that each vertex is incident to at most 2 distinct colors. In the maximum edge 2-coloring problem, the input consists of an undirected graph, and the goal is to find an edge 2-coloring with the maximum number of colors.

The maximum edge 2-coloring is known to be APX-hard and the best known  approximation factor is 2. Approximation algorithms with a factor better than 2 are known only for particular classes of graphs that have a perfect matching.

We provide a 9/5 approximation algorithm for the maximum edge 2-coloring problem on bipartite graphs.

12:15-12:45 Catalin Zara. Title: Depth-Parity Constraints for Binary Search Trees

Abstract: Let n\geq 1 be a positive integer. The depth-parity trace of a binary search tree T with nodes labeled by [n]={1,2,  .... , n} is the bitstring w given by w(i) =1 if i is on an even-level node in T, and 0 otherwise, recording the labels of even-depth nodes. A recursive Interval Dynamic Programming algorithm to determine whether a given bitstring of length n is the depth-parity trace of a binary search tree has time-complexity O(n^3) and space-complexity O(n^2).

We present a novel algorithmic framework that reduces those bounds to

linear (O(n)) time and space complexities. We introduce and prove a  combinatorial equivalent of a constraint for the depth-parity trace of a binary search tree, and use that description to construct a linear time and space algorithm for validating bitstrings as depth-parity traces. We compute the number of depth-parity traces of binary search trees, and show that the density of those traces converges exponentially fast to 1.

This is joint work with Gabriel Istrate, University of Bucharest, Romania.

12:45-15:15 LUNCH

15:15-16:15 Marina Meila (Plenary)  Title: How to prove that a clustering is (approximately) correct

Abstract: You have clustered your data with K-means. But K-means only finds local optima: how can you know if there isn't a very different and better clustering? There is a surprising and recent answer to this question. When the data is "well clustered" one can get a guarantee, **on mathematical grounds only**, that the found clustering is the "correct" one.

We introduce the Sublevel Set (SS) method, a generic method to obtain guarantees of near-optimality and uniqueness (up to small perturbations) for a clustering. The guarantees are deterministic and practically computable. The SS method can be instantiated for a variety of clustering loss functions for which convex relaxations exist. We demonstrate the applicability of this method by obtaining distribution free guarantees for K-means and spectral clustering on realistic data sets.

Then, we pose a similar problem for estimating mixtures of Gaussians, and we show partial results on distribution free guarantees for the model parameters.

This work is part of Marina Meila's current research program "Unsupervised Validation for Unsupervised Learning", which aims to design broad-ranging, mathematically and statistically grounded methods to interpret, verify and validate the output of Unsupervised Machine Learning algorithms with a minimum of assumptions and of human intervention.

Joint with Hanyu Zhang.

16:15-16:45 BREAK

16:45-17:15 Florin Manea. Title: Optimal Enumeration of Regular Pattern Matches

Abstract: Enumerating all matches of a regular expression with capture variables (variable regex, for short) to a document is a fundamental task in textual information extraction, e.g., in connection to document spanners. State-of-the-art results [Amarilli et al., ACM TODS 2021] show how the matches of a variable regex, representable by a sequential variable-set automaton, to a document can be enumerated with delay constant in the size of the document and polynomial in the size of the query, after a preprocessing requiring time linear in the size of the document and polynomial in the size of the query.

We consider here the matching problem for regular expressions with capture variables which can be represented as regular patterns: w_0x_0 w_1x_1 \cdots w_{k}x_k w_{k+1}, where, for i in {0,\ldots,k+1}, w_i is a string of terminal letters and, for i in {0,\ldots,k}, x_i is a variable. This problem naturally lies in the intersection of information extraction and stringology, as it can also be seen as computing all the ways in which k+1 given strings w_0,\ldots,w_{k+1} occur, in this order and without overlaps, in a given text T. We provide an optimal enumeration algorithm for this problem. After a preprocessing requiring linear time in the size of the document T and the size of the query pattern alpha, we can enumerate all matches with worst-case constant delay (in combined complexity, i.e., both in the document- and the query-size).

Based on: Paweł Gawrychowski, Florin Manea, Stefan Siemer, Paul Sarnighausen-Cahn. “Optimal Enumeration of Regular Pattern Matches,” To appear in PODS 2026.

17:15-17:45 Mihai Prunescu. Title: "Formulas for the prime counting number and the n-th prime"

Abstract: We develop arithmetic terms expressing the functions pi(n) and p(n). The joint work with Joseph Shunia can be read in the preprint https://arxiv.org/abs/2412.14594.

Saturday May 23

9:00-9:30 László Kozma. Title: Improved time-space tradeoff for TSP via extremal combinatorics.

Abstract: The best known exact algorithms for the traveling salesman problem (TSP)

achieve 2^n time and 2^n space, or 4^n time and polynomial space (Bellman, Held, Karp, resp., Savitch, Gurevich, Shelah). An easy combination of the two approaches yields a tradeoff between T^n time and S^n space at certain points of the curve T*S = 4.

We give a new tradeoff scheme that improves upon this for all 2<T<4, in particular yielding a minimum of T*S < 3.572. The result hinges on a natural, and perhaps overlooked combinatorial question about the existence of certain set systems.

Joint work with Justin Dallant.

9:30-10:30 Alex Andoni (Plenary). Title: Nearest Neighbor Search Problems in LLMs

Abstract: Long a foundational primitive for classification and retrieval, high-dimensional Nearest Neighbor Search (NNS) keeps resurfacing in many roles across the modern LLM pipeline. This talk explores three such roles: as the retrieval engine powering RAG systems; as a Kernel Density Estimation (KDE) problem underlying the KV cache problem in transformers; and as a route toward a sub-quadratic attention mechanism. Along the way, I will highlight many open problems.

10:30-11:15 BREAK

11:15-11:45 Ioana Bercea

11:45 -12:45 Cosmin Pohoata (Plenary)

12:45-14:45 LUNCH

14:45 -15:15 Dan Ghica

15:15 - 15:45 Gabriel Istrate

15:45-16:30 Open problems/discussion.