MPI-INF Talks

In the Maximum Independent Set of Objects problem, we are given an n-vertex planar graph G and a family D of N objects, where each object is a connected subgraph of G. The task is to find a subfamily F ⊆ D of maximum cardinality that consists of pairwise disjoint objects. This problem is NP-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane.

In this talk, we show an OPT^ε-approximation algorithm for the problem that runs in time N^{O(1 / ε²)}  n^O(1), for any ε > 0.

Based on the SODA '24 paper with Jana Cslovjecsek and Michał Pilipczuk. Available at https://arxiv.org/abs/2310.20325.

The notion of envy-freeness up to any item (EFX) is considered to be the most fascinating fairness concept in fair division of indivisible items. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. introduced a promising relaxation of EFX, called epistemic EFX (EEFX). We say an allocation to be EEFX if, for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes EFX-satisfied. Caragiannis et al. [IJCAI'23] prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive? We address this important open question by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations.

The talk is based on the joint AAAI-25 paper with Hannaneh Akrami. Available at https://arxiv.org/abs/2405.14463.

Two fundamental classes of finite automata are deterministic and nondeterministic ones (DFAs and NFAs). Natural intermediate classes arise from bounds on an NFA's allowed ambiguity, i.e. number of accepting runs per word: unambiguous, finitely ambiguous, and polynomially ambiguous finite automata. It is known that deciding whether a given NFA is unambiguous and whether it is polynomially ambiguous is possible in quadratic time, and deciding finite ambiguity is possible in cubic time. I will prove matching lower bounds showing these running times to be optimal, assuming popular fine-grained complexity hypotheses.

Based on the joint work with Karolina Drabik, Fabian Frei, Filip Mazowiecki and Karol Węgrzycki. Available at https://arxiv.org/abs/2501.14725.

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism. In this work we study space-bounded machines with access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Despite this heavy restriction, many recent works have shown the power of catalytic space, its utility in designing classical space-bounded algorithms, and surprising connections between catalytic computation and derandomization.

Our main result is that bipartite maximum matching (MATCH) can be computed in catalytic logspace (CL) with a polynomial time bound (CLP). Moreover, we show that MATCH can be reduced to the lossy coding problem for NC circuits (LOSSY[NC]). This has consequences for matching, catalytic space, and derandomization.

Based on the joint FOCS'25 work with Ian Mertz. Available at https://arxiv.org/abs/2504.09991.