Discrete Algorithm Insights Seminar RMU

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.

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

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.

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.