Together with Mateusz Skomra we offer a 12 month postdoctoral fellowship on the topic
. The position will be funded through the POPML4PS chair of the ANITI AI cluster. Click
Hidden Monotonicity: Explaining Deep Neural Networks via their DC Decomposition
with Jakob Paul Zimmermann (arxiv)
CVPR 2026
Abstract
It has been demonstrated in various contexts that monotonicity leads to better explainability in neural networks. However, not every function can be well approximated by a monotone neural network. We demonstrate that monotonicity can still be used in two ways to boost explainability. First, we use an adaptation of the decomposition of a trained ReLU network into two monotone and convex parts, thereby overcoming numerical obstacles from an inherent blowup of the weights in this procedure. Our proposed saliency methods - SplitCAM and SplitLRP - improve on state of the art results on both VGG16 and Resnet18 networks on ImageNet-S across all Quantus saliency metric categories. Second, we exhibit that training a model as the difference between two monotone neural networks results in a system with strong self-explainability properties.
Arithmetic Circuits and Neural Networks for Regular Matroids
with Christoph Hertrich, Stefan Kober (arxiv)(slides)
IPCO 2026
Abstract
We prove that there exist uniform (+,*,/)-circuits of size O(n^3) to compute the basis generating polynomial of regular matroids on n elements. By tropicalization, this implies that there exist uniform (max,+,−)-circuits and ReLU neural networks of the same size for weighted basis maximization of regular matroids. As a consequence in linear programming theory, we obtain a first example where taking the difference of two extended formulations can be more efficient than the best known individual extended formulation of size O(n^6) by Aprile and Fiorini. Such differences have recently been introduced as virtual extended formulations. The proof of our main result relies on a fine-tuned version of Seymour's decomposition of regular matroids which allows us to identify and maintain graphic substructures to which we can apply a local version of the star-mesh transformation.
Exact Characterization of Aggregate Flexibility via Generalized Polymatroids
with Karan Mukhi, Alessandro Abate (arxiv)(publication)
IEEE Transactions on Smart Grid 2026
Abstract
There is growing interest in utilizing the flexibility in populations of distributed energy resources (DER) to mitigate the intermittency and uncertainty of renewable generation and provide additional grid services. To enable this, aggregators must effectively represent the flexibility in the populations they control to the market or system operator. A key challenge is accurately computing the aggregate flexibility of a population, which can be formally expressed as the Minkowski sum of a collection of polytopes - a problem that is generally computationally intractable. However, the flexibility polytopes of many DERs exhibit structural symmetries that can be exploited for computational efficiency. To this end, we introduce generalized polymatroids - a family of polytope - into the flexibility aggregation literature. We demonstrate that individual flexibility sets belong to this family, enabling efficient computation of their Minkowski sum. For homogeneous populations of DERs we further derive simplifications that yield more succinct representations of aggregate flexibility. Additionally, we develop an efficient optimization framework over these sets and propose a vertex-based disaggregation method, to allocate aggregate flexibility among individual DERs. Finally, we validate the optimality and computational efficiency of our approach through comparisons with existing methods.
Lower bounds for ranking-based pivot rules
with Yann Disser, Matthew Maat, Nils Mosis (arxiv)(conference)
STACS 2026
Abstract
The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games each are prominent open problems in their respective fields. While numerous natural candidates for efficient rules have been eliminated, all existing lower bound constructions are tailored to individual or small sets of pivot rules. We introduce a unified framework for formalizing classes of rules according to the information about the input that they rely on. Within this framework, we show lower bounds for \emph{ranking-based} classes of rules that base their decisions on orderings of the improving pivot steps induced by the underlying data. Our first result is a superpolynomial lower bound for strategy improvement, obtained via a family of sink parity games, which applies to memory-based generalizations of Bland's rule that only access the input by comparing the ranks of improving edges in some global order. Our second result is a subexponential lower bound for policy iteration, obtained via a family of Markov decision processes, which applies to memoryless rules that only access the input by comparing improving actions according to their ranks in a global order, their reduced costs, and the associated improvements in objective value. Both results carry over to the simplex method for linear programming.
Quotients of M-convex sets and M-convex functions
with Marie-Charlotte Brandenburg, Ben Smith (arxiv)
Combinatorial theory
Abstract
We unify the study of quotients of matroids, polymatroids, valuated matroids and strong maps of submodular functions in the framework of Murota's discrete convex analysis. As a main result, we compile a list of ten equivalent characterizations of quotients for M-convex sets, generalizing existing formulations for (poly)matroids and submodular functions. We also initiate the study of quotients of M-convex functions, constructing a hierarchy of four separate characterizations. Our investigations yield new insights into the fundamental operation of induction, as well as the structure of linking sets and linking functions, which are generalizations of linking systems and bimatroids.
Depth-Bounds for Neural Networks via the Braid Arrangement
with Moritz Grillo, Christoph Hertrich (arxiv)
NeurIPS 2025
Abstract
We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on Rd. While the question has been resolved in special cases, the best known lower bound in general is still 2. We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan. For such neural networks, we prove a non-constant lower bound of Omega(loglogd) hidden layers required to exactly represent the maximum of d numbers. Additionally, under our assumption, we provide a combinatorial proof that 3 hidden layers are necessary to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far. Finally, we show that a natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that a rank-3 maxout layer followed by a rank-2 maxout layer is sufficient to represent the maximum of 7 numbers.
Reducing Stochastic Games to Semidefinite Programming
with Manuel Bodirsky, Mateusz Skomra (arxiv)(conference)
ICALP 2025
Abstract
We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon's simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity games can all be reduced to semidefinite programming.
The Real Tropical Geometry of Neural Networks
with Marie-Charlotte Brandenburg, Guido Montúfar (arxiv)(publication)
Transactions on Machine Learning Research (2024)
Abstract
We consider a binary classifier defined as the sign of a tropical rational function, that is, as the difference of two convex piecewise linear functions. The parameter space of ReLU neural networks is contained as a semialgebraic set inside the parameter space of tropical rational functions. We initiate the study of two different subdivisions of this parameter space: a subdivision into semialgebraic sets, on which the combinatorial type of the decision boundary is fixed, and a subdivision into a polyhedral fan, capturing the combinatorics of the partitions of the dataset. The sublevel sets of the 0/1-loss function arise as subfans of this classification fan, and we show that the level-sets are not necessarily connected. We describe the classification fan i) geometrically, as normal fan of the activation polytope, and ii) combinatorially through a list of properties of associated bipartite graphs, in analogy to covector axioms of oriented matroids and tropical oriented matroids. Our findings extend and refine the connection between neural networks and tropical geometry by observing structures established in real tropical geometry, such as positive tropicalizations of hypersurfaces and tropical semialgebraic sets.
Oriented Matroids from Triangulations of Products of Simplices
with Marcel Celaya, Chi Ho Yuen (arxiv)(publication)
Selecta Mathematica (2024)
Abstract
We introduce a construction of oriented matroids from a triangulation of a product of two simplices. For this, we use the structure of such a triangulation in terms of polyhedral matching fields. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex, which might be of independent interest. In particular, we generalize this using the language of matroids over hyperfields, which gives a new approach to construct matroids over hyperfields. A recurring theme in our work is that various tropical constructions can be extended beyond tropicalization with new formulations and proof methods.
-
The Worst-Case Complexity of Symmetric Strategy Improvement
with Tom van Dijk, Matthew Maat (arxiv)(conference)
CSL 2024
Abstract
Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve two-player games on directed graphs such as parity games and mean payoff games. In contrast to the usual well-known strategy improvement algorithm, it iterates over strategies of both players simultaneously. The symmetric version solves the known worst-case examples for strategy improvement quickly, however its worst-case complexity remained open.
We present a class of worst-case examples for symmetric strategy improvement on which this symmetric version also takes exponentially many steps. Remarkably, our examples exhibit this behaviour for any choice of improvement rule, which is in contrast to classical strategy improvement where hard instances are usually hand-crafted for a specific improvement rule. We present a generalized version of symmetric strategy iteration depending less rigidly on the interplay of the strategies of both players. However, it turns out it has the same shortcomings.
Face posets of tropical polyhedra and monomial ideals
with Ben Smith (journal)(arxiv)
The Electronic Journal of Combinatorics (2023)
Abstract
We exhibit several posets arising from commutative algebra, order theory, tropical convexity as potential face posets of tropical polyhedra, and we clarify their inclusion relations. We focus on monomial tropical polyhedra, and deduce how their geometry reflects properties of monomial ideals. Their vertex-facet lattice is homotopy equivalent to a sphere and encodes the Betti numbers of an associated monomial ideal.
Tropical Positivity and Determinantal Varieties
with Marie-Charlotte Brandenburg, Rainer Sinn (journal)(arxiv)
Algebraic Combinatorics (2023)
Abstract
We initiate the study of positive-tropical generators as positive analogues of the concept of tropical bases. Applying this to the tropicalization of determinantal varieties, we develop criteria for characterizing their positive part. We focus on the study of low-rank matrices, in particular matrices of rank 2 and 3. Moreover, in the case square-matrices of corank 1, we fully classify the signed tropicalization of the determinantal variety, even beyond the positive part.
-
Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes
with Christian Haase, Christoph Hertrich (arxiv)(conference)
ICLR 2023
Abstract
We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that \(\lceil\log_2(n)\rceil\) hidden layers are indeed necessary to compute the maximum of n numbers, matching known upper bounds. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry. The integrality assumption implies that these Newton polytopes are lattice polytopes. Then, our depth lower bounds follow from a parity argument on the normalized volume of faces of such polytopes.
On the Correlation Gap of Matroids
with Edin Husić, Zhuan Khye Koh, László A. Végh (journal)(arxiv)(conference)
IPCO 2023, Mathematical Programming (2024)
Abstract
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is 1−1/e, and this is tight even for simple matroid rank functions.
We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes. Previous work relied on implicit correlation gap bounds for problems such as list decoding and approval voting.
Tropical Carathéodory with Matroids
with Raman Sanyal (journal)(arxiv)
Discrete & Computational Geometry (2023)
Abstract
Bárány's colorful generalization of Carathéodory's Theorem combines geometrical and combinatorial constraints. Kalai-Meshulam (2005) and Holmsen (2016) generalized Bárány's theorem by replacing color classes with matroid constraints. In this note, we obtain corresponding results in tropical convexity, generalizing the tropical colorful Carathéodory Theorem of Gaubert-Meunier (2010). Our proof is inspired by geometric arguments and is reminiscent of matroid intersection. In particular, we show that the topological approach fails in this setting. We also discuss tropical colorful linear programming and show that it is NP-complete. We end with thoughts and questions on generalizations to polymatroids, anti-matroids as well as examples and matroid simplicial depth.
Interior point methods are not worse than Simplex
with Xavier Allamigeon, Daniel Dadush, Bento Natura, László A. Végh (journal)(arxiv)(conference)
FOCS 2022, SIAM Journal on Computing 2025
Abstract
Whereas interior point methods provide polynomial-time linear programming
algorithms, the running time bounds depend on bit-complexity or condition
measures that can be unbounded in the problem dimension. This is in contrast
with the simplex method that always admits an exponential bound. We introduce a
new polynomial-time path-following interior point method where the number of
iterations also admits a combinatorial upper bound $O(2^{n} n^{1.5}\log n)$ for
an $n$-variable linear program in standard form. This complements previous work
by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a
family of instances where any path-following method must take exponentially
many iterations.
The number of iterations of our algorithm is at most $O(n^{1.5}\log n)$ times
the number of segments of any piecewise linear curve in the wide neighborhood
of the central path. In particular, it matches the number of iterations of any
path following interior point method up to this polynomial factor. The overall
exponential upper bound derives from studying the `max central path', a
piecewise-linear curve with the number of pieces bounded by the total length of
$2n$ shadow vertex simplex paths.
Our algorithm falls into the family of layered least squares interior point
methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to
previous layered least squares methods that partition the kernel of the
constraint matrix into coordinate subspaces, our method creates layers based on
a general subspace providing more flexibility. Our result also implies the same
bound on the number of iterations of the trust region interior point method by
Lan, Monteiro, and Tsuchiya (SIOPT 2009).
Generalized permutahedra and positive flag Dressians
with Michael Joswig, Dante Luber, Jorge Alberto Olarte (journal)(arxiv)(conference)
FPSAC 2022, International Mathematics Research Notices (2023)
Abstract
We study valuated matroids, their tropical incidence relations, flag matroids and total positivity.
Our techniques employ the polyhedral geometry of the hypersimplices, the regular permutahedra and their subdivisions.
Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
with Zhuan Khye Koh (journal)(conference)(arxiv)(video)
MFCS 2022, Logical Methods in Computer Science 2025
Abstract
Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (2017). The central combinatorial object underlying these approaches is a universal tree, as identified by Czerwiński et al. (2019). By providing a quasi-polynomial lower bound on the size of universal trees, they have highlighted a barrier that must be overcome by all existing approaches to attain polynomial runtime. This is due to the existence of worst case instances which force these algorithms to explore a large portion of the tree.
As an attempt to overcome this barrier, we propose a strategy iteration framework which can be applied on any universal tree. It is at least as fast as its value iteration counterparts, while allowing one to take bigger leaps in the universal tree. Value iteration - asymptotically the fastest known algorithm for parity games - is a repeated application of operators associated with arcs in the game graph to obtain the least fixed point. Our main technical contribution is an efficient method for computing the least fixed point of operators associated with arcs in a strategy subgraph. This is achieved via a careful adaptation of shortest path algorithms to the setting of ordered trees. By plugging in the universal tree of Jurdziński and Lazić (2017), or the Strahler universal tree of Daviaud et al. (2020), we obtain instantiations of the general framework that take time O(mn^2log nlog d) and O(mn^2log^3 nlog d) respectively per iteration.
Patchworking Oriented Matroids
with Marcel Celaya, Chi Ho Yuen (journal)(arxiv)(video)
Journal of the London Mathematical Society (2022)
Abstract
In a previous work, we gave a construction of (not necessarily realizable) oriented matroids from a triangulation of a product of two simplices. In this follow-up paper, we use a variant of Viro's patchworking to derive a topological representation of the oriented matroid directly from the polyhedral structure of the triangulation, hence finding a combinatorial manifestation of patchworking besides tropical algebraic geometry. We achieve this by rephrasing the patchworking procedure as a controlled cell merging process, guided by the structure of tropical oriented matroids. A key insight is a new promising technique to show that the final cell complex is regular.
On complete classes of valuated matroids
with Edin Husić, Ben Smith, László A. Végh (journal)(arxiv)(conference)
ACM-SIAM Symposium on Discrete Algorithms 2022, TheoretiCS (2024)
Abstract
We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We refute the refinement of a 2003 conjecture by Frank, exhibiting valuated matroids that are not R-minor. The family of counterexamples is based on sparse paving matroids. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.
-
Tropical Ehrhart Theory and Tropical Volume
with Matthias Schymura
(publication)(arxiv)(slides)
Research in the Mathematical Sciences, 7(30) (2020)
Abstract
We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposition is complemented by a brief study of arising complexity questions.
Matching fields and lattice points of simplices
with Ben Smith (publication)(arxiv)(slides)
Advances in Mathematics, 370 (2020), 107232
Abstract
We show that the Chow covectors of a linkage matching field define a bijection between certain degree vectors and lattice points, and we demonstrate how one can recover the linkage matching field from this bijection.
This resolves two open questions from Sturmfels and Zelevinsky (1993) on linkage matching fields. For this, we give an explicit construction that associates a bipartite incidence graph of an ordered partition of a common set to each lattice point in a dilated simplex.
Given a triangulation of a product of two simplices encoded by a set of spanning trees on a bipartite node set, we similarly prove that the bijection from left to right degree vectors of the trees is enough to recover the triangulation. As additional results, we show a cryptomorphic description of linkage matching fields and characterise the flip graph of a linkage matching field in terms of its prodsimplicial flag complex. Finally, we relate our findings to transversal matroids through the tropical Stiefel map.
Abstract tropical linear programming
(publication)(arxiv)
The Electronic Journal of Combinatorics (2020)
Abstract
In this paper we develop a combinatorial abstraction of tropical linear programming. This generalizes the search for a feasible point of a system of min-plus-inequalities. We obtain an algorithm based on an axiomatic approach to this generalization. It builds on the introduction of signed tropical matroids based on the polyhedral properties of triangulations of the product of two simplices and the combinatorics of the associated set of bipartite graphs with an additional sign information. Finally, we establish an upper bound for our feasibility algorithm applied to a system of min-plus-inequalities in terms of the secondary fan of a product of two simplices. The appropriate complexity measure is a shortest integer vector in a cone of the secondary fan associated to the system.
Signed tropical convexity
with László A. Végh (publication)(arxiv)(slides)
11th Innovations in Theoretical Computer Science Conference (ITCS 2020), LIPIcs, Volume 151 (2020), pp. 24:1-24:35
Abstract We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.
Monomial tropical cones for multicriteria optimization
with Michael Joswig (publication)(arxiv)(slides)
SIAM J. Discrete Math., 34(2) (2020), 1172-1191.
Abstract
We present an algorithm to compute all n nondominated points of a multicriteria discrete optimization problem with d objectives using at most O(n^(\lfloor d/2 \rfloor)) scalarizations. The method is similar to algorithms by Przybylski, Gandibleux, and Ehrgott and by Klamroth, Lacour, and Vanderpooten with the same complexity. As a difference, our method employs a tropical convex hull computation, and it exploits a particular kind of duality which is special for the tropical cones arising. This duality can be seen as a generalization of the Alexander duality of monomial ideals.
Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
with Michael Joswig, Benjamin Lorenz, Benjamin Schröter (publication)(arxiv)
Mathematical Aspects of Computer and Information Sciences: 6th International Conference (MACIS 2015), Revised Selected Papers, LNCS Volume 9582 (2016), pp 429-445
Abstract We describe the implementation of a subfield of the field of formal Puiseux series in polymake. This is employed for solving linear programs and computing convex hulls depending on a real parameter. Moreover, this approach is also useful for computations in tropical geometry.
Weighted digraphs and tropical cones
with Michael Joswig
(publication)
Linear Algebra Appl. 501 (2016), 304-343.
Abstract
This paper is about the combinatorics of finite point configurations in the tropical projective space or, dually, of arrangements of finitely many tropical hyperplanes. Moreover, arrangements of finitely many tropical halfspaces can be considered via coarsenings of the resulting polyhedral decompositions of R^d. This leads to natural cell decompositions of the tropical projective space TP_min^(d-1). Our method is to employ a known class of ordinary convex polyhedra naturally associated with weighted digraphs. This way we can relate to and use results from combinatorics and optimization. One outcome is the solution of a conjecture of Develin and Yu (2007).
MatchTheNet - An Educational Game on 3-Dimensional Polytopes
with Michael Joswig, Benjamin Lorenz, Rico Raber (publication)(game homepage)
33rd International Symposium on Computational Geometry (SoCG 2017), LIPIcs, Volume 77 (2017), pp 66:1--66:5
Abstract We present an interactive game which challenges a single player to match 3-dimensional polytopes to their planar nets. It is open source, and it runs in standard web browsers.
