With the fast growth of networks and the rapid increase of the size of our data, distributed algorithms in networks will play a crucial role in our future and will be relevant in almost all aspects of life. This project aims at advancing our understanding of the foundational aspects of these areas. Algorithms operating in such settings have to deal with different forms of communication restriction, e.g., caused by large distances between computers in a network or bandwidth restrictions of communication links. Objectives. The main goal of this project is to provide a fundamental theory and to significantly extend the understanding of the role of communication restrictions for distributed computations. Approach & Level of Originality. Our approach is two-fold: On the one hand, we aim at developing new communication efficient distributed algorithms addressing central open questions in the area, such as under-standing the role of randomness. This requires us to go well beyond the current state-of-the-art, which we, for example, achieve via novel methods for derandomization and new graph decompositions that are optimized for bandwidth restricted settings. On the other hand, we aim at determining the limits of distributed computation. A core goal is to identify universal underlying reasons for the hardness of distributed optimization. While such central points of hardness are well-known in the centralized world, such a result would be novel in the distributed setting. Besides, we aim at solving a number of smaller, easier problems that would serve as stepping stones towards these bigger goals. Communication efficient algorithms are often robust in the sense that they yield solutions in different computational models. Hence, in the long term, this project will also impact other areas such as massively parallel computation algorithms, sublinear algorithms, streaming, and local computation algorithms. Primary researchers involved. The research team consists of the PI (Ass. Prof. Yannic Maus, TU Graz) and two PhD students funded by this project. Additionally, we aim to continue established collaborations with international experts useful to our project and also to extend our collaboration network.

Discrete mathematics studies the mathematical properties of structures that can be accurately represented by a computer. It is omnipresent in everyday life: encryption techniques, for example when paying with a credit card or when surfing the Internet, are based on methods of discrete mathematics. Another example are optimization problems, for example when designing train timetables or when planning industrial supply chains. More generally, discrete mathematics forms the theoretical backbone of computer science - an understanding of how an algorithm works is impossible without mathematics. The consortium of our doc.fund brings together colleagues from TU Graz and the University of Graz and focuses on building bridges between sub-areas of discrete mathematics. Our consortium emerges from the doctoral program “Discrete Mathematics”, which was financially supported by the FWF from 2010 to 2024 and has firmly anchored research in this area in Graz and made it internationally visible. We concentrate on fundamental research without losing sight of application areas. We define the term discrete mathematics broadly, extending into the areas of number theory, algebra and theoretical computer science, and thus cover a wide range of research fields. The specific topics in the doc.funds project range from the question of which polynomials can be represented as a sum of squares, to computability in networks with limited information, to the problem of which surfaces can be made from textile material. Each doctoral position in this doc.funds project is supervised equally by two members of the consortium. In most cases, the support takes place at different institutes and the proposed projects lie at the intersection of their expertise. This means we work on innovative and highly relevant research topics with optimal team support. In addition, we are continuing our proven tools for excellent doctoral training, for example our lively weekly seminar, the opportunity for long-term stays at foreign research institutions, and a successful mentoring program. This results in excellent training, both for an academic career and for many sectors of the economy. In fact, graduates of our predecessor program hold responsible positions in a wide variety of areas, such as consulting, software development, insurance and data analysis.