Discrete Algorithm Insights Seminar RMU

Assuming P ≠ NP, the worst case runtime for any algorithm solving an NP-hard must be super-polynomial. But what is the lowest runtime we can get? Before one can even hope to approach this question, a more provoking one presents itself: Since for many problems simple “brain-dead” algorithms are still the fastest known, maybe these are already optimal? In this survey talk we give three examples of research lines studying this type of question for the Traveling Salesperson Problem, the Set Cover problem, and (if time permits) a classical scheduling problem with precedence constraints.

Maker-Breaker games are sequential games with perfect information played by two players, called Maker and Breaker. For $n,q \in \mathbb{N}$ and a subgraph $C$ of the complete graph $K_n$ the Maker-Breaker $C$-game is played as follows. Alternately Maker claims an edge and thereafter Breaker claims up to $q$ edges of $K_n$ until every edge has been claimed by one of the two players. If at the end of the game the graph of Maker-edges contains a copy of $C$, Maker wins the game, otherwise Breaker wins.

Bednarska and Łuczak (1999) showed that there exists constants $c_0$ and $c_1$ such that for large enough $n$ Maker has a winning strategy if $q \leq c_0 n^{1/m(C)}$ and Breaker has a winning strategy if $q \geq c_1 n^{1/m(C)}$ where $m(C) = \max_{\substack{H \subseteq C, |V(H)| \geq 3}} \frac{|E(H)|-1}{|V(H)|-2}$. Thus the asymptotics of the game has been determined exactly, but unfortunately the constants implicitly given in the proof of Bednarska and Łuczak are magnitudes apart from each other. For example for the $C_3$ game the constant $c_0$ is smaller than $10^{-5}$ and the constant $c_1$ is larger than $10^4$.

Bednarska and Łuczak conjectured that these constants could be chosen arbitrarily close to each other. This conjecture is open for every graph $C$ which contains a cycle and for the most graphs there are not even good constants known. These constants have a significant meaning: powerful strategies lead to good constants and the smaller the gap between these constants is, the closer the players are to optimal play. In the intensively studied case where $C$ is a cycle of length 3 Chvátal and Erdős (1978) showed that Maker can win the game if $q \leq \sqrt{2}\sqrt{n}$ and Breaker can win if $q \geq 2\sqrt{n}$.

Recently Glazik and Srivastav (2022) introduced a new potential function which gives a winning strategy for Breaker if $q>\sqrt{8/3} \sqrt{n}$, which is considered a breakthrough result. We were able to generalize this potential function concept to cycles of arbitrary length, a class of games for which previously no good strategies with explicit constants were known. We also give a constructive strategy for Maker in the $C_4$-game which leads to the first good constant $c_0$ for this game.

I will discuss recent developments at the intersection of formal language theory and machine learning, especially with the goal to understand the expressiveness of transformers. Among others, I will discuss results connected my recent work (e.g. from ICLR’24).

Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW).

We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1,1)). We show that this result is tight - ex-ante WEF is incompatible with any stronger ex-post WEF relaxation.

In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.

Random graphs are commonly used as network models and, as such, often capture typical features shared amongst graphs from some (application) domain. In algorithmics, we can use such models to improve our theoretical understanding of the practical performance of graph algorithms, e.g., by encoding input classes for average case analyses as random graphs.

Especially in the algorithm engineering community, random graphs additionally gained attention as a controllable and versatile data source for experimental campaigns. However, generating such data-sets at scale is a non-trivial task in itself.

In this talk, we introduce a selection of basic algorithmic techniques used in practical graph generators and highlight how the presumed model of computation informs the design of state-of-the-art generators. Most ideas are also applicable to sample discrete objects beyond random graphs.