MPI-INF Talks

The following talks are from 13:45-14:00, from August 10 (Monday) to August 13 (Thursday).

• Kurt Mehlhorn: Who Gets What? Fair Division of Indivisible Goods
• Anouk Duyster: Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
• Benjamin Berendsohn: Permutation patterns in streams
• Simon Döring: Wait, Have We Seen this Graph Before?

A set of indivisible goods, e.g., a car, a house, a toothbrush, etc., has to be split among a set of agents in a fair manner. Each agent has its own valuation function for sets of goods. What constitutes a fair allocation? When does a fair allocation exist? If it exists, can we compute it efficiently? Can we approximate fair allocations?

One of the notions of fairness is envy-freeness: nobody should get more than I do. For indivisible goods, envy-freeness cannot be achieved in general. Think of two persons and one good which both like. The good has to be given to one of the persons and the other person will envy. Envy-freeness up to any good (EFX) is a mild relaxation. One person may envy another person, but upon removal of any good from the other person's bundle, the envy goes away. Imagine the following hypothetical dialogue. A person says to his brother. You got a house, a car, and a toothbrush. I envy you, but this is OK, because if I discard the toothbrush, I do not envy you anymore.

I will discuss the existence question for EFX-allocations. They exist for three agents and additive valuations, and they do not exist for three agents and general monotone valuations.

Based on joint work with M. Afshinmehr, H. Akrami, N.Alon, A. Ashuri, B. Chaudhury, J. Garg, M. Hoefer, T. Kavitha, P. Mahmoundkhan, R. Mehta, P. Misra, M. Schmalhofer, A. Sgouritsa, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland.

A Random Access query to a string T of length n over an alphabet of size sigma asks for the character T[i] at a given position i. In O(n log(sigma)) bits of space, this fundamental task admits constant-time queries. While this is optimal in the worst case, much research has focused on compressible strings, hoping for smaller data structures that still admit efficient queries.

We investigate the grammar-compressed setting, where T is represented by a straight-line grammar. Our main result is a general trade-off that optimizes Random Access time as a function of string length n, grammar size (the total length of productions) g, alphabet size sigma, data structure size M, and word size w=Omega(log n) of the word RAM model. For any M with g log n < Mw < n log sigma, we show an O(M)-size data structure with query time O(log(n log sigma / (M w)) / log(M w / (g log n))). Remarkably, we also prove a matching unconditional lower bound that holds for all parameter regimes except very small grammars and relatively small data structures.

Previous work focused on query time as a function of n only, achieving O(log n) time using O(g) space [Bille et al.; SIAM J. Comput. 2015] and O(log n / log log n) time using O(g log^(epsilon) n) space for any constant epsilon > 0 [Belazzougui et al.; ESA'15], [Ganardi, Jeż, Lohrey; J. ACM 2021]. The only tight lower bound [Verbin and Yu; CPM'13] was Omega(log n / log log n) for w=Theta(log n), n^Omega(1) ≤ g ≤ n^(1-Omega(1)), and M=g log^(Theta(1)) n. In contrast, our result yields tight bounds in all relevant parameters and almost all regimes.

Our data structure admits efficient deterministic construction. It relies on novel grammar transformations that generalize contracting grammars [Ganardi; ESA'21]. Beyond Random Access, its variants support substring extraction, rank, and select.

Based on joint work with Tomasz Kociumaka presented at ICALP 2026.

We study a fundamental decremental dynamic graph problem: tree sums in forests. In this problem, we need to maintain a vertex-weighted forest of size n under edge deletions, weight updates, and the query about the current sum of weights in a specified connected component (tree) of the forest. The problem can be solved in O(log n) time per update/query using standard dynamic forest data structures like top trees, even if additionally edge insertions are allowed. We investigate whether the deletion-only problem can be solved faster.

In this talk, I will show a data structure with O(n) preprocessing time and O(log^* n) time per operation, based on a micro-macro tree decomposition (Alstrup et al., 1997). Given enough time, I will also discuss an asymptotically universally optimal algorithm for the problem.

Based on a joint work with Benjamin Berendsohn; available at https://arxiv.org/abs/2605.06555.

If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for graph problems called “algorithms with isomorphic priors”.
Solving a graph problem in this model involves two phases:

1. Preprocessing phase: analyzes prior graphs G_1,..., G_k along with the (previously computed) exact optimal values OPT(G_i).
2. Query phase: Given a new graph H then either (a) output the exact solution OPT(H), or (b) correctly reports that H is not isomorphic to any G_i.

Now, can we avoid computing OPT(H) from scratch when H is isomorphic to some G_i? If so, how can we archive this? Can we solve some NP-complete problems quickly in our new model? And what about breaking fine-grained lower bounds? Are there problems that are canonically hard in this model, and if so, can we find some kind of relation between them? All these will be answered in this talk.

Based on joint work with Dani Dorfman, Martin Herold, Danupon Nanongkai, Daniel Neuen, Joachim Spoerhase and Zihang Wu.