Projections, Redundancy and Parallelism in lrslib
Given an H-representation of a polyhedron (a system of linear inequalities), two fundamental problems are to remove redundancies and compute projections. Related problems include determining whether two representations share the same projection. Recent examples of such problems motivated the development of several approaches to deal with them, which have been implemented in the lrslib package. This is joint work with David Avis.
Nonarchimedean optimization
In this talk, we give an basic introduction on how to optimize a continuous, real-valued function on a nonarchimedean space via gradient descent on its Berkovich analytification. Our motivation stems from the analysis of hierarchical data, such as files in a database, computers in a network, words in a language, or even tokens of an LLM. Mathematically, such data can be described as a finite metric space, and hierarchical means that the metric satisfies the strong triangle inequality. Therefore, hierarchical data cannot be isometrically embedded into euclidean space, but they can be embedded into a nonarchimedean space. Unfortunately, nonarchimedean spaces are totally disconnected and thus unsuitable for techniques such as gradient descent. We explain how this can be fixed theoretically by passing to a suitable subset of the Berkovich analytification and demonstrate how it can be done in practice using a mix of tropical and non-archimedean geometry.
The length of coherent monotone paths on polytopes admits a central limit theorem
To solve a linear program given by a polytope P and a direction c, the simplex method traverses a path along the graph of P. This path is increasing (for the scalar product) against c. The length of this path is an important measure of the complexity of the simplex method. Numerous previous articles focused on the longest paths, or, following the footsteps of Borgwardt, computed the average length of a path according to a certain probabilistic model. We want to understand more precisely how this length is distributed, i.e. how many paths there are of each length. In particular, it was conjectured by De Loera that the number of paths counted according to their length form a unimodal sequence. On the one side, we provide natural examples for which this conjecture holds; but on the other side, we disprove this conjecture. More importantly, we show that De Loera is “statistically almost correct” by proving that the length of (coherent) paths on a random polytope (whose vertices are chosen uniformly on the sphere) admits a central limit theorem.
Computing optimal lattice polygons
I will describe dynamic programming algorithms for computing smallest-area convex lattice n-gons (OEIS:A070911 and A089187), the number of smooth lattice polygons with given area (A366409), and similar counting and optimization problems.
Codegree of stable set polytopes
The codegree of a lattice polytope is a fundamental invariant in discrete geometry.
In this talk, we study the codegree of the stable set polytope associated with a graph. In particular, we give an upper bound and lower bound on the codegree by using invariants of the associated graph.
Moreover, we provide explicit formulas for the codegree in two special cases: when the graph is a line graph and when it is an h-perfect graph. This talk is based on joint work with Koji Matsushita.