Logo of DAIS RMU

Discrete Algorithm Insights Seminar RMU

The Discrete Algorithm Insights Seminar at the Rhine-Main-Universities is a regular in-person seminar for researchers and students interested in discrete algorithms and related topics, such as graph theory, complexity, and optimization.

Everyone is welcome to attend without registration! If possible, please subscribe to our mailing list so that we have a rough estimate for the number of participants.

Upcoming talks

  • July 12, 2024
    TU Darmstadt (Campus Stadtmitte)
    Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt  (show on map)
  • 13:00
    Anna Zych-Pawlewicz (University of Warsaw)
    Randomization techniques for online bipartite matching
  • 14:15
    Maximilian Gläser (TU Darmstadt)
    Lower bounds for Branch-and-Bound with General Disjunctions via Monotone Real Interpolation

Past talks

  • June 21, 2024
    Goethe University Frankfurt (Campus Bockenheim)
    H IV | Hörsaaltrakt Bockenheim, Gräfstraße 50-54, 60486 Frankfurt am Main  (show on map)
  • 13:00
    Anthony Lin (RPTU Kaiserslautern-Landau)
    Understanding the expressive power of transformers through the lens of formal language theory
    [show abstract]
    [hide]
    Abstract:

    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).

  • 14:15
    Marco Schmalhofer (Goethe University Frankfurt)
    Best of Both World Fair Division with Entitlements
    [show abstract]
    [hide]
    Abstract:

    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.

  • May 17, 2024
    Johannes Gutenberg University Mainz
    Raum 03-428 | Staudingerweg 9, 55128 Mainz  (show on map)
  • 13:00
    Martin Grohe (RWTH Aachen)
    The Descriptive Complexity of Graph Neural Networks
    [show abstract]
    [hide]
    Abstract:

    Graph neural networks (GNNs) are deep learning models for graph data that play a key role in machine learning on graphs. A GNN describes a distributed algorithm carrying out local computations at the vertices of the input graph. Typically, the parameters governing this algorithm are acquired through data-driven learning processes.

    After introducing the basic model, in this talk we will focus on the expressiveness of GNNs: which functions on graphs or their vertices can be computed by GNNs? An intriguing and nontrivial facet of this inquiry is that GNNs are “analog” computation models operating on and with real numbers. Nevertheless, we can give precise characterisations of the expressiveness of GNNs in terms of Boolean circuits and logic, that is, computation models of classical (descriptive) complexity theory.

  • 14:15
    Annamária Kovács (Goethe University Frankfurt)
    A proof of the Nisan-Ronen conjecture
    [show abstract]
    [hide]
    Abstract:

    Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.

    Joint work with George Christodoulou and Elias Koutsoupias

  • February 2, 2024
    Johannes Gutenberg University Mainz
    Raum 01-211 | Binger Str. 14-16, 55122 Mainz  (show on map)
  • 13:00
    Martin Skutella (TU Berlin)
    Transshipments over time and submodular functions
    [show abstract]
    [hide]
    Abstract:

    Network flows over time are a fascinating generalization of classical (static) network flows, introducing an element of time. They naturally model problems where travel and transmission are not instantaneous and flow may vary over time. Not surprisingly, flow over time problems turn out to be more challenging to solve than their static counterparts. In this talk, we mainly focus on the efficient computation of transshipments over time in networks with several source and sink nodes with given supplies and demands, which is arguably the most difficult flow over time problem that can still be solved in polynomial time.

  • 14:15
    Rebecca Steiner (Johannes Gutenberg University Mainz)
    Broadcasting on Random Recursive Trees
    [show abstract]
    [hide]
    Abstract:

    In the broadcasting problem on trees, a {0,1}-message, originating in an unknown node, is passed along the tree with a certain error probability q. The goal is to estimate the original message without knowing the order in which the nodes were informed. A variation of the problem is considering this broadcasting process on a randomly growing tree, which Addario-Berry et al. have investigated for uniformly recursive and linear preferential attachment trees. We extend their studies to the entire group of very simple increasing trees, as well as shape exchangeable trees, using the connection between them and other stochastic processes with memory effects.

  • January 19, 2024
    TU Darmstadt (Campus Stadtmitte)
    Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt  (show on map)
  • 13:00
    Isolde Adler (University of Bamberg)
    Logic and property testing
    [show abstract]
    [hide]
    Abstract:

    Property testing (for a property P) asks for a given graph, whether it has property P, or is “structurally far” from having that property. A “testing algorithm” is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as “extremely efficient”, making them relevant in the context of large data sets.

    In this talk I will present recent positive and negative results about testability of properties definable in first-order logic and monadic second-order logic on classes of bounded-degree graphs.

    This is joint work with Polly Fahey, Frederik Harwath, Noleen Köhler and Pan Peng.

  • 14:15
    Irene Heinrich (TU Darmstadt)
    All interesting graphs are symmetric
  • November 24, 2023
    Goethe University Frankfurt (Campus Bockenheim)
    H 3 | Hörsaaltrakt Bockenheim, Gräfstraße 50-54, 60486 Frankfurt am Main  (show on map)
  • 13:00
    Pascal Schweitzer (TU Darmstadt)
    Symmetries of Combinatorial Structures
  • 14:15
    Manuel Penschuck (Goethe University Frankfurt)
    Sampling Random Graphs at Scale
    [show abstract]
    [hide]
    Abstract:

    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.

  • November 3, 2023
    TU Darmstadt (Campus Stadtmitte)
    Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt  (show on map)
  • 13:00
    Kurt Mehlhorn (Max Planck Institute for Informatics)
    Who Gets What? Fair Division of Indivisible Goods
    [show abstract]
    [hide]
    Abstract:

    A set of indivisible goods, e.g., a car, a house, a toothbrush, …, 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?

    The talk is based on joint work with H. Akrami, N.Alon, B. Chaudhury, J. Garg, M. Hoefer, T. Kavitha, R. Mehta, P. Misra, M. Schmalhofer, A. Sgouritsa, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland that appeared in EC20, EC21, EC23, JACM 23, FSTTCS 20, SODA 21, AAAI 22, IJCAI 23, and SICOMP 22.

  • 14:15
    Júlia Baligács (TU Darmstadt)
    The online graph exploration problem

About

DAIS is organized by the Consortium on Discrete Algorithm Insights (CoDa Insights). The Consortium consists of all interested researchers and students from the Rhine-Main-Universities, and is currently coordinated by the following faculty members: