-
The Worst-Case 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 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 (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 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 (arxiv)(conference)
FOCS 2022
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
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 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 (arxiv)(conference)
ACM-SIAM Symposium on Discrete Algorithms 2022
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.
The Real Tropical Geometry of Neural Networks
with Marie-Charlotte Brandenburg, Guido Montúfar (arxiv)
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.
Quotients of M-convex sets and M-convex functions
with Marie-Charlotte Brandenburg, Ben Smith (arxiv)
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.
Signed tropical halfspaces and convexity
with Mateusz Skomra (arxiv)(video)
Abstract
We extend the fundamentals for tropical convexity beyond the tropically positive orthant expanding the theory developed by Loho and Végh (ITCS 2020). We study two notions of convexity for signed tropical numbers called 'TO-convexity' (formerly 'signed tropical convexity') and the novel notion 'TC-convexity'. We derive several separation results for TO-convexity and TC-convexity. A key ingredient is a thorough understanding of TC-hemispaces - those TC-convex sets whose complement is also TC-convex. Furthermore, we use new insights in the interplay between convexity over Puiseux series and its signed valuation. Remarkably, TC-convexity can be seen as a natural convexity notion for representing oriented matroids as it is arises from a generalization of the composition operation of vectors in an oriented matroid.
Oriented Matroids from Triangulations of Products of Simplices
with Marcel Celaya, Chi Ho Yuen (arxiv)
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.
