Publications

2025

1. Probabilistic algorithm for computing all local minimizers of Morse functions on a compact domain

   Mohab Safey El Din, Georgy Scholten, and Emmanuel Trélat

   2025

   Pre-print

   Abs Journal HAL PDF

   The paper describes an algorithm to compute local minimizers of Morse functions on a unit cube, using probabilistic techniques and polynomial approximations.

2023

1. Exact solutions in log-concave maximum likelihood estimation

   Alexandros Grosdos, Alexander Heaton, Kaie Kubjas, and 3 more authors

   Advances in Applied Mathematics, 2023

   Abs Journal

   We study probability density functions that are log-concave. Despite the space of all such densities being infinite-dimensional, the maximum likelihood estimate is the exponential of a piecewise linear function determined by finitely many quantities, namely the function values, or heights, at the data points. We explore in what sense exact solutions to this problem are possible. First, we show that the heights given by the maximum likelihood estimate are generically transcendental. For a cell in one dimension, the maximum likelihood estimator is expressed in closed form using the generalized W-Lambert function. Even more, we show that finding the log-concave maximum likelihood estimate is equivalent to solving a collection of polynomial-exponential systems of a special form. Even in the case of two equations, very little is known about solutions to these systems. As an alternative, we use Smale’s α-theory to refine approximate numerical solutions and to certify solutions to log-concave density estimation.

2022

1. Sparse Moments of Univariate Step Functions and Allele Frequency Spectra

   Zvi Rosen, Georgy Scholten, and Cynthia Vinzant

   Vietnam Journal of Mathematics, Apr 2022

   Nonlinear Algebra (Part I) - Dedicated to Bernd Sturmfels on the occasion of his 60th birthday.

   Abs Journal

   We study the univariate moment problem of piecewise-constant density functions on the interval [0,1] and its consequences for an inference problem in population genetics. We show that, up to closure, any collection of n moments is achieved by a step function with at most n −\thinspace1 breakpoints and that this bound is tight. We use this to show that any point in the n th coalescence manifold in population genetics can be attained by a piecewise constant population history with at most n −\thinspace2 changes. Both the moment cones and the coalescence manifold are projected spectrahedra and we describe the problem of finding a nearest point on them as a semidefinite program.

2019

1. Semi-inverted linear spaces and an analogue of the broken circuit complex

   Georgy Scholten, and Cynthia Vinzant

   Algebraic Combinatorics, Apr 2019

   Abs Journal

   The image of a linear space under inversion of some coordinates is an affine variety whose structure is governed by an underlying hyperplane arrangement. In this paper, we generalize work by Proudfoot and Speyer to show that circuit polynomials form a universal Gröbner basis for the ideal of polynomials vanishing on this variety. The proof relies on degenerations to the Stanley–Reisner ideal of a simplicial complex determined by the underlying matroid, which is closely related to the external activity complex defined by Ardila and Boocher. If the linear space is real, then the semi-inverted linear space is also an example of a hyperbolic variety, meaning that all of its intersection points with a large family of linear spaces are real.

2017

1. Resultants over commutative idempotent semirings I: Algebraic aspect

   Hoon Hong, Yonggu Kim, Georgy Scholten, and 1 more author

   Journal of Symbolic Computation, Apr 2017

   Abs Journal

   The resultant theory plays a crucial role in computational algebra and algebraic geometry. The theory has two aspects: algebraic and geometric. In this paper, we focus on the algebraic aspect. One of the most important and well known algebraic properties of the resultant is that it is equal to the determinant of the Sylvester matrix. In 2008, Odagiri proved that a similar property holds over the tropical semiring if one replaces subtraction with addition. The tropical semiring belongs to a large family of algebraic structures called commutative idempotent semiring. In this paper, we prove that the same property (with subtraction replaced with addition) holds over an arbitrary commutative idempotent semiring.