TU Berlin

Fachgebiet Algorithmische AlgebraKolloquium (Oberseminar)

Inhalt des Dokuments

zur Navigation

Kolloquium (Oberseminar)

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. (For students: Please note that you cannot earn any ECTS!)

Abstracts

Fewnomial Theory on Average

Speaker: Alperen Ergür

If a univariate polynomial has t nonzero terms then it has at most (t-1) many positive real zeros said René Descartes in his La Géométrie around 1637. Since then it's an intriguing puzzle to find the correct multivariate generalization of Descartes' rule. Around 1980, Askold G. Khovanskii showed that a system of real polynomials with n variables and t nonzero terms has at most exponentially many non-degenerate positive real zeros in terms of t. A conjecture attributed to Anatoli Kushnirenko claims that the correct upper bound is of order t^n. This remains open even for n=2! We show that Kushnirenko's prediction holds true for random sparse polynomial systems with Gaussian coefficients of arbitrary variance.
This is joint work with Peter Bürgisser and Josue Tonelli-Cueto.

Shape Reconstruction from Moments

Speaker: Philipp di Dio

Based on recent advances in the theory of moments, especially the Caratheodory numbers, we present the latest results on shape reconstruction from moments based on a new and unified method, the derivatives of moments. Our approach simplifies old and gives new results.
This is joint work with Mario Kummer.

Vandermonde Varieties, Mirrored Spaces and the Homology of symmetric semialgebraic sets

Speaker: Cordian Riener

The abstract is available as pdf-file.

Computing the Homology of Semialgebraic Sets. II: General Formulas

Speaker: Felipe Cucker

This talk will be based on the preprint of the same title (arXiv:1903.10710), which is joint work with Peter Bürgisser and Josue Tonelli Cueto.

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. This extends the previous work of the authors in arXiv:1807.06435 to arbitrary semialgebraic sets. 
All previous algorithms proposed for this problem have doubly exponential complexity (and this is so for almost all input data).

Efficient algorithms for moment polytopes and the null cone problem from invariant theory

Speaker: Peter Bürgisser

Suppose a reductive group G acts linearly on a finite dimensional complex vector space V. The corresponding null cone, which may be thought of the set of ``singular objects'', consists of those vectors that cannot be distinguished from the zero vector by means of polynomial invariants. The null cone was introduced by Hilbert in his seminal work on invariant theory around 1900.
Quite surprisingly, the computational problem of testing membership to the null cone turned out to be of relevance for geometric complexity theory, quantum information theory, and other areas. Notably, a thorough study of the null cone for the simultanous left/right action on tuples of matrices was crucial for finding a deterministic polynomial time algorithm for verifying algebraic identies.
Despite the algebraic nature of the problem, numerical optimization algorithms seem to be the most efficient general methods for solving the null cone problem. This also applies to the related problem of testing membership to moment polytopes, which e.g., generalizes Horn's problem on the eigenvalues of sums of matrices.

The goal of the talk is to provide an overview on these developments.

Random points on algebraic manifolds

Speaker: Paul Breiding

Consider the set of solutions to a system of polynomial equations in many variables. An algebraic manifold is an open submanifold of such a set. I will discuss a new method for computing integrals and sampling from distributions on algebraic manifolds. This method is based on intersecting the manifold with linear spaces. It produces i.i.d. samples, works in the presence of multiple connected components, and is simple to implement. I discuss applications to computational statistical physics and topological data analysis.
This is joint work with Orlando Marigliano from MPI Leipzig.

Real and Complex Line Arrangements

Speaker: Ali Ulas Özgür Kisisel

The abstract is available as pdf-file.

Singular tuples of matrices is not a null cone

Speaker: Visu Makam

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING(n,m), consisting of all m-tuples of n x n matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING(n,m) will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation.
A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: SING(n,m) is not the null cone of any reductive group action! This stands in stark contrast to a non-commutative analog of this variety, and points to an inherent structural difficulty of SING(n,m).
This is joint work with Avi Wigderson.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe