EF1 – Extracting dynamical Laws from Complex Data

The field of Extremal Combinatorics is concerned with the largest or smallest possible size of discrete structures satisfying some, usually highly structured and regular, properties. The dynamic underlying these problems, despite being well-structured, is incredibly complicated and understanding such complex systems is a major challenge for contemporary Mathematics. Often even a simple probabilistic argument provides a good or even the best known lower bound.

It is natural to try computational approaches in order to gain insights into the nature of these problems. However, in most cases a straight-forward exhaustive search on small examples will very quickly fall into the trap of combinatorial chaos as the search space grows exponentially. Often one small instance can be handled by hand, while the next larger is already out of reach even on modern computers. The right computational approach can however gain insights on problems in Extremal Combinatorics: the most notable example is Razborov’s introduction of Flag Algebras.

We intend to study the applicability of recent incredible advancement in Artificial Intelligence to problems from Extremal Combinatorics. Machine Learning algorithms are solving tasks that were unthinkable up until recently. Many of these tasks, such as recent advancements in the game of Go, can be described as combinatorial problems whose complexity originates from simple rules. Applying these methods to Extremal Combinatorics is a largely untapped field and we are studying to what degree techniques coming from Reinforcement Learning can be used to tame the combinatorial chaos. Results stemming from this research likewise also have the potential to reflect back on the area of Machine Learning: combinatorial problems can provide challenging environments to study the efficacy of different methods and to see how they handle complex environments with a sparse rewards structure.