
The WorstCase Complexity of Symmetric Strategy Improvement
with Tom van Dijk, Matthew Maat (arxiv)(conference)
Abstract
Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve twoplayer games on directed graphs such as parity games and mean payoff games. In contrast to the usual wellknown strategy improvement algorithm, it iterates over strategies of both players simultaneously. The symmetric version solves the known worstcase examples for strategy improvement quickly, however its worstcase complexity remained open.
We present a class of worstcase 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 handcrafted 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 vertexfacet lattice is homotopy equivalent to a sphere and encodes the Betti numbers of an associated monomial ideal.
Tropical Positivity and Determinantal Varieties
with MarieCharlotte Brandenburg, Rainer Sinn (journal)(arxiv)
Algebraic Combinatorics (2023)
Abstract
We initiate the study of positivetropical 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 lowrank matrices, in particular matrices of rank 2 and 3. Moreover, in the case squarematrices 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 (arxiv)(conference)
IPCO 2023
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 finegrained 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. KalaiMeshulam (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 GaubertMeunier (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 NPcomplete. We end with thoughts and questions on generalizations to polymatroids, antimatroids 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 (arxiv)(conference)
FOCS 2022
Abstract
Whereas interior point methods provide polynomialtime linear programming
algorithms, the running time bounds depend on bitcomplexity 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 polynomialtime pathfollowing 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 pathfollowing 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
piecewiselinear 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
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 (conference)(arxiv)(video)
MFCS 2022
Abstract
Parity games have witnessed several new quasipolynomial 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 quasipolynomial 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 followup 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 (arxiv)(conference)
ACMSIAM Symposium on Discrete Algorithms 2022
Abstract
We characterize a rich class of valuated matroids, called Rminor 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 Rminor. 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 minplusinequalities. 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 minplusinequalities 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:124: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 FourierMotzkin elimination without the nonnegativity restriction on the variables. This leads to a MinkowskiWeyl 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), 11721191.
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 429445
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), 304343.
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^(d1). 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 3Dimensional 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:166:5
Abstract We present an interactive game which challenges a single player to match 3dimensional polytopes to their planar nets. It is open source, and it runs in standard web browsers.