Bürgisser’s home is algebraic complexity theory, which studies the complexity of fundamental computational problems within an algebraic framework of computation. This includes the design and analysis of efficient algorithms for algebraic problems, a topic belonging to computer algebra. Algebraic complexity adds to this the quest for lower complexity bounds, an enterprise genuine to theoretical computer science. The tools needed to establish such lower bounds cover a large spectrum of mathematics: ranging from combinatorics to representation theory, topology, and algebraic geometry. A current focus of the research group is on understanding geodesic optimization in the presence of symmetry described by group actions. This leads to a fascinating interplay of concepts from convex optimization with ideas from invariant theory and computational complexity. There are applications in a suprisingly wide range of areas.  We are also concerned with the probabilistic analysis of numerical algorithms and condition numbers. We made progress on the complexity of numerically solving systems of polynomial equations (Smale’s 17th problem). We also contributed to the theory of condition numbers in convex optimization.

Geometry is a rich source of natural graph theoretic problems (graph drawing, graphs with geometric representation). Geometric graph theory studies combinatorial and geometric properties of spatial networks, i.e. graphs embedded in space. They are relevant in many of the standard subjects of graph theory whenever the location of vertices matters, including transportation, mobile phone, and biological neural networks. Shedding light on their extremal graph theoretic properties are key to the design of more efficient algorithms. The study of the dimension and related parameters of partially ordered sets, in particular containment orders, is an active direction with many interesting open problems.

Michael Joswig is interested in all aspects of polyhedral, tropical and algorithmic geometry, and this includes topics such as optimization, combinatorial topology and applications to biology. He is also active in designing and applying mathematical software (polymake, OSCAR).

The area of discrete optimization is concerned with the efficient solution of optimization problems over discrete structures such as networks and matroids with applications in traffic, telecommunication, and economics. Besides classical optimization problems also equilibrium problems and multi-agent systems in these areas are studied.

Algorithmic Intelligence aims at computing “smart” decisions. The A²IM department is applying advanced AI methods from Mathematical Optimization and Machine Learning to explore new smart algorithmic solutions for real-world problems. Our research is concerned, in particular, with better planning, extension, and control of vital and complex infrastructure networks. Mixed integer linear and non-linear optimization, modelling and optimization of the real-world planning and control of infrastructure networks. In general, industrial applications of discrete optimization. Computation on large graph structured data sets. Discrete optimization problems in relation to Quantum Computing. Development of discrete optimization solvers. There are connections to RTA 3: Quantum portfolio optimization, RTA 6: Scientific Computing, and RTA 8: Large scale data analysis.

László Kozma is interested in the design and analysis of algorithms, especially for fundamental combinatorial structures, such as permutations, graphs, partial orders. He particularly focuses on the adaptivity and instance-optimality of algorithms and data structures, on online settings where uncertainty plays a key role, and on the interplay between combinatorial and geometric structure and algorithm efficiency.

We study the complexity of geometric problems, both from an upper-bound view, developing new algorithms for problems that have geometric inputs, and from a lower-bound view, showing that such algorithms are unlikely to exist. In the past, we have focused on algorithms for shape matching, for graphs that have a geometric representation, and on the complexity of geometric problems in high-dimensions. For example, we have developed new algorithms and lower bounds for computing the Frechet-distance between to polygonal curves, a longstanding problem that has been studied in the community for decades, and we have developed a very useful dynamic data structure for locating nearest neighbors in a point set that changes dynamically, for very general distance functions. Along the way, we also study foundational problems from discrete geometry that we encounter during our research. For example, we have recently improved a long-standing bound on the length of a longest non-crossing bichromatic path in a biclored point set in convex position. Along these lines our research connects to RTA 5.

Schweikardt's research interest aim at theoretical computer science with an emphasis on Logic, Database Theory, and Complexity Theory. She is particularly interested in the connections between these areas. For instance, the theoretical foundations of modern database systems deeply rely on various connections to mathematical logic. Methods from Finite Model Theory play an important role, in particular, for the exploration of the expressive power and the computational complexity of database query languages. Finite Model Theory also exposes a connection between Logic and Complexity Theory by showing a close correspondence between the amount of time or space resources that are necessary for solving a problem algorithmically (computational complexity) and the complexity (or, the richness) of a formal language that is capable of describing the problem (descriptive complexity).

Martin Skutella’s research is focused on Combinatorial Optimization, Efficient Algorithms, and Complexity. He is particularly interested in network flows and more general network optimization problems as well as all kinds of discrete optimization problems from various application fields. The main methodological approaches in his research are exact and approximation algorithms that build on combinatorial insights as well as polyhedral relaxations, with ties to RTA 5. He also studies the expressivity of neural networks and related complexity questions, with ties to RTA 8.

Extremal and Probabilistic Combinatorics investigates the extremal behaviour of parameters over a family of discrete structures with a given property. Motivation for parameters and properties of interest routinely arise from the modelling of discrete real-life phenomena. The employed methods, besides Combinatorics, often draw from other mathematical disciplines, such as Algebra, Discrete Probability, and Topology. Applications and connections to other areas include Combinatorial Optimization, Complexity, Machine Learning and Algorithms.