Projects

Active Projects

Sums of Nonnegative Circuit Polynomials and Combinatorics in Polynomial Optimization

The project concerns studying sums of nonnegative circuit polynomials (SONC) and their use for sparse polynomial optimization. These concepts regard key ideas in the rapidly growing interplay of combinatorics, convexity and and non-linear optimization. The goal is to develop new combinatorial methods for the construction of certificates of nonnegativity in sparse contexts and the interaction of the SONC cone with a variety of combinatorial concepts. Specific working directions concern exactness results, convex-algebraic questions, generalized combinatorial models for the optimization and nonnegativity of sparse polynomials as well as selected applications.
The project is part the DFG priority programme SPP 2458 Combinatorial Synergies.

PIs: Timo de Wolff, Thorsten Theobald (Goethe University Frankfurt)
Involved researchers in our group: Timo de Wolff, Nik Rieke
Funding: Deutsche Forschungsgemeinschaft (DFG)
Duration: 2024 - 2026

Past Projects

Emmy Noether Project "New Certificates of Nonnegativity and Their Application in Science and Engineering"

This project concerns a new certificate of nonnegativity called sums of nonnegative circuit polynomials (SONC). Nonnegativity of real polynomials is a notoriously hard problem, which is central for polynomial optimization.
In practice, one attacks such problems using certificates of nonnegativity. In 2014, Iliman and de Wolff suggested a new certificate called sums of nonnegative circuit polynomials (SONC), which can be computed via relative entropy programming, and which are not sums of squares (SOS) in general.
In this Emmy Noether project we achieved various milestones to establish SONCs as a certificate of nonnegativity. Among other results, we give a description of the algebraic boundary of the SONC cone. We show combinatorial properties of maximal mediated sets, which provide information when SONCs are also SOS. We provide an implementation of initial algorithms for SONC computations and show experimentally on a large set of random polynomials that it provides fast runtimes in practice with moderately worse bounds than SOS. Furthermore, we apply SONCs to various problems in sciences and engineering: We use SONC to establish new bounds on parameter spaces for phosphorylation. We show that SONCs are a meaningful certificate in terms of proof systems analyzing algorithms in theoretical computer science, and show various results regarding containment and comparison of such proof systems. Moreover, we show that SONCs do not admit a Putinar-like Positivstellensatz. As a third application, we provide initial results for applying SONCs to compute Lyapunov functions for certifying stability in dynamical systems.

PIs: Timo de Wolff
Involved researchers in our group: Janin Heuer, Timo de Wolff, Oğuzhan Yürük
Mentors: Michael Joswig (at TU Berlin; 2017-2019).
Funding: Emmy Noether programme of the Deutsche Forschungsgemeinschaft (DFG)
Duration: 2017 - 2023

ProvideQ: Quantum Readiness for Optimization Providers

Quantum algorithms have the potential to massively increase the performance of solution methods for practically relevant combinatorial optimisation problems. However, very few companies can master quantum technologies themselves. This is the reason for ProvideQ's approach: instead of working with end users, we co-operated with leading service providers who make advanced algorithmic methods available to industry. Developments made here thus achieve an economic multiplier effect.
In order to prepare German providers of algorithmic services for the quantum age, we worked on two levels. (1) We expanded the existing modelling systems of two service providers with a quantum toolbox. This enables a broad group of users to describe their problems in a domain-specific language, for which quantum mechanical and hybrid solution strategies can then be found. (2) In selected areas of integer and convex optimisation, as well as for optimisation problems under uncertainty, we made approaches that have so far only been described theoretically practicable and developed new algorithms. We were guided by use cases and example data from the project partners and made the results freely accessible.

PIs: Sebastian Stiller (TU Braunschweig), Sándor Fekete (TU Braunschweig), Ina Schäfer (Karlsruher Institut für Technologie), David Gross (Universität zu Köln), Richard Kueng (JKU Linz), Tobias Osborne (Leibniz Universität Hannover), Timo de Wolff
Involved researchers in our group: Sabrina Ammann, Janin Heuer, Birte Ostermann, Timo de Wolff
Industry Partners: 4flow AG, GAMS Software GmbH
Funding: German Ministry for Economic Affairs and Climate Action (BMWK)
Duration: 2022 - 2025

Deep Learning for Imaging in Nano and Quantum Science

The interdisciplinary project Deep Learning for imaging in nano and quantum science involved experimental physics, electrical engineering, and mathematics. We applied artificial intelligence to two important fields in physics in reduced dimensions: Quantum dot nanostructures and molecules on surfaces. In combining expertise of both, application and theory, we developed deep learning procedures, which can process the numerous measured images and lead to a deeper understanding as well as better control of fabrication of these systems.

PIs: Andreas Hangleiter, Uta Schlickum, Markus Etzkorn, Tim Fingscheidt, Dirk Lorenz, Uwe Rossow, Timo de Wolff (all TU Braunschweig)
Involved researchers in our group: Mandy Stritzke, Timo de Wolff
Funding: VW-Stiftung and the state of Lower Saxony (Land Niedersachsen; Niedersächsisches Vorab-Programm)
Duration: 2021 - 2024

Classifying Polynomial Maps by Means of Polyhedral Geometry

This project concerned the study of polynomial maps from the complex plane to itself. Two such maps are said to have the same topological type whenever one is obtained from the other by simultaneously composing with homeomorphisms on the target and source spaces. There is a lack of effective methods for deciding on whether or not two polynomial maps have the same topological type. This impedes progress on key questions in affine algebraic geometry and applied nonlinear algebra where polynomial maps play a central role. We employed tropical geometry to develop effective methods for describing various topological and algebraic invariants of polynomial maps.

PIs and involved researchers in our group: Boulos El Hilany
Mentors: Timo de Wolff
Funding: Walter Benjamin programme of the Deutsche Forschungsgemeinschaft (DFG).
Duration: 2021 - 2023

German Young Academy

The German Junge Akademie is an institution that elects ten early career researchers and artists for a five year membership. It is a place of interdisciplinary work and admits its members substantial freedom. Part of the academy membership is the opportunity to create and realize interdisciplinary projects. During the years of membership, our group received funding for various projects funded by the Young Academy, occassionally joint with external partners. Highlights were the event series "Die 7 größten Abenteuer der Mathematik" and the exhibition "Unendlichkeit - Leere - Lebendigkeit", which are described in the Events section. Other examples were the projects "Blood-brain dynamics and machine learning" and "Evaluation of pool based test methods for COVID-19 testing", which lead to interdisciplinary journal publications.

PIs: Timo de Wolff (joint with various others, depending on the particular project)
Involved researchers in our group: Janin Heuer, Mandy Stritzke (in individual projects)
Funding: Die Junge Akademie.
Duration: 2019 - 2024