Combinatorics, Graph Theory, Combinatorial Optimization, Applied Mixed Integer Linear Optimization, Complexity, and Algorithms
Discrete structures (graphs, hypergraphs, matroids, posets) are of paramount importance in modelling a wide variety of reallife scenarios; e.g. graphs are ubiquitous in describing all sorts of networks, let it be computer, transportation, social, or biological, while posets are the natural model for hierarchical systems. The study of the fundamental properties and behavior of these structures, together with the algorithmic and optimization tasks involving them have an enormous impact on all parts of our society, and form the subject of Discrete Mathematics/Optimization. Complexity is a central topic both in mathematics and in computer science. It appears in various forms, including combinatorial complexity (number) of mathematical structures, description complexity (the possibility of encoding a structure succinctly or visualizing it clearly); and, algorithmic complexity (running time, storage). In recent years it has become apparent that the different approaches to complexity are interwoven, and significant new insights are possible by combining several viewpoints. The Berlin Discrete Mathematics community integrates several aspects of complexity into a broad and interconnected research and training program.
Berlin research groups
Algebraic and Geometric Methods in Data Analysis The main research interests of Carlos Améndola are in the field of Applied Algebraic Geometry and Nonlinear Algebra, with a particular focus on Algebraic Statistics. While linear algebra has been the foundation for a large part of mathematics, nonlinear algebra goes beyond linear equations to consider polynomial models across the mathematical sciences. Perhaps surprisingly at first, many tools from algebraic geometry, commutative algebra, convex and discrete geometry and combinatorics are particularly useful to solve problems arising in optimization, probability and statistics. Carlos Améndola's research aims to explore and exhibit these interdisciplinary connections, revealing not only applicable techniques for data analysis, but also new intriguing theoretical questions to be answered. Some keywords are: Gaussian mixtures, maximum likelihood degree, moment varieties, path signatures and graphical models. 
TU Berlin 

Network Optimization The network optimization department at ZIB is working on the solution of problems in public, rail, air, and individual transport as well as logistics. Collaborations with industry are centered in the MobilityLab of the Research Campus MODAL, research projects in Math+'s Application Area 3 Networks. The group tries to bring discrete optimization together with methods from geometry and algebra, from numerical optimization, and from data science, to solve complex problems that integrate several factors that were hitherto treated separately, and to develop large scale technique that push the frontier of what is possible. 
FU Berlin and ZIB 

Algebraic Complexity TheoryBü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. 
TU Berlin 

Combinatorial Optimization Under UncertaintyA prerequisite for classic combinatorial optimization is the assumption that problem parameters are known in advance and remain fixed. However, uncertainty is a prevalent and challenging facet of many realworld decision environments where combinatorial optimization is typically applied, such as logistics, network design, and scheduling. This motivates the study of combinatorial optimization under uncertainty where decisions must be made given only incomplete information about the problem instance. Depending on the amount and type of available information, different models of uncertainty, such as stochastic or online, are studied. 
TU Berlin 

Geometric Graph TheoryGeometry 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. 
TU Berlin 

Polyhedral, Tropical and Algorithmic GeometryMichael 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). 
TU Berlin 

Max Klimm  Discrete OptimizationThe 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 multiagent systems in these areas are studied. 
TU Berlin 
Algorithmic Intelligence (AI)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 realworld problems. Our research is concerned, in particular, with better planning, extension, and control of vital and complex infrastructure networks. Mixed integer linear and nonlinear optimization, modelling and optimization of the realworld 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. 
TU Berlin and ZIB 

Data Structures, Algorithms, CombinatoricsLá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 instanceoptimality 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. 
FU Berlin (Computer Science) 

Computational Geometry, ComplexityWe study the complexity of geometric problems, both from an upperbound view, developing new algorithms for problems that have geometric inputs, and from a lowerbound 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 highdimensions. For example, we have developed new algorithms and lower bounds for computing the Frechetdistance 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 longstanding bound on the length of a longest noncrossing bichromatic path in a biclored point set in convex position. Along these lines our research connects to RTA 5. 
FU Berlin (Computer Science) 

Computational Geometry and Discrete MathematicsGünter Rote has worked on motionplanning problems and geometric reconfiguration problems both with a view on practical applicability (robot motion) as well as theoretically. He also works on combinatorial counting enumeration problems and algorithms for combinatorial structures, such as polyominoes or pseudoline arrangements, both analytically and with the help of computers. Other topics of his interest are graph drawing and problems from combinatorial geometry. 
FU Berlin (Computer Science)  
Logic and Complexity TheorySchweikardt'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). 
HU Berlin (Computer Science)  
Combinatorial Optimization, Efficient Algorithms, and ComplexityMartin 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. 
TU Berlin  
Extremal and Probabilistic CombinatoricsExtremal 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 reallife 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. 
FU Berlin 
Links to other areas
There are natural, strong collaborative ties to the following groups:
Discrete and Computational Topology projects of RTA 1:
Pavle Blagojevic
Discrete Geometry groups of RTA 5:
Guilia Codenotti, Christian Haase, Martin Henk, Michael Joswig, Günter Ziegler
Discrete Aspects in Machine Learning and large scale Data Analysis in RTA 8:
Sebastian Pokutta
Core Courses
The BMS Core Courses in Area 4 and details about their content can be found under "Course Program":
Area 4  Core Courses
Advanced Courses
Topics for typical advanced courses include: Extremal Combinatorics, The Probabilistic Method, Constructive Combinatorics, Positional Games, Order Theory, Algebraic Combinatorics, Topological Methods; Combinatorial Algorithms, Approximation Algorithms, OnlineAlgorithms, Mechanism Design, Online Optimization, Scheduling, Periodic Timetabling and Passenger Routing, Integer and MixedInteger Programming, Convex Optimization and Applications.
The current advanced courses are listed under "Course Program":
Area 4  Advanced Courses