General Info
In our Kolloquium on algorithmic mathematics and complexity theory, guests and members of the group present current topics about their research.
If you are interested in (some of) the talks you are welcome to join us. To do so, please write an email to Philipp Reichenbach.
For students: Please note that you cannot earn any ECTS!
The Kolloquium usually takes place on Wednesday at 3pm sharp (German time). Our research group meets in MA 316 to follow the talk. Usually, the talks have a hybrid format with an additional Zoom link.
Abstracts
Counting zeros of random fewnomial systems
Speaker: Peter Bürgisser
We consider systems of n Laurent polynomials in n variables with the same fixed set A of monomials and independent random real coefficients, say standard Gaussian. What can we say about the expected number N(A) of positive zeros? The analogous question can be raised over the p-adics. Based on recent work in [B, Kulkarni, Lerario], we show that the expected number N_p(A) of p-adic zeros can be well understood. For instance, for fixed Newton polytope P= conv(A), the maximum of N_p(A) can be neatly expressed in terms of the h-vector of P.
These ideas from convex geometry also help to better understand the problem over the reals: indeed, we found a more conceptual derivation of the upper bound in [B, Erguer, Tonelli-Cueto]. More insights are expected to come (work in progress).
Deterministic Approximation Algorithms for Volumes of Spectrahedra
Speaker: Mahmut Levent Doğan
We give a method for computing asymptotic formulas and approximations for the volumes of spectrahedra, based on the maximum-entropy principle from statistical physics.Spectrahedra can be described as affine slices of the convex cone of positive semi-definite (PSD) matrices, and the method yields efficient deterministic approximation algorithms and asymptotic formulas whenever the number of affine constraints is sufficiently dominated by the dimension of the PSD cone.
The approach is inspired by the work of Barvinok and Hartigan who used an analogous framework for approximately computing volumes of polytopes. Spectrahedra, however, possess a remarkable feature not shared by polytopes, a new fact that we also prove: central sections of the set of density matrices (the quantum version of the simplex) all have asymptotically the same volume. This allows for very general approximation algorithms, which apply to large classes of naturally occurring spectrahedra.
The talk is based on an arXiv preprint with the same title which is a joint work with Jonathan Leake and Mohan Ravichandran.