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. To do so, please write an email to Philipp Reichenbach (reichenbach at tu-berlin.de).

For students: Please note that you cannot earn any ECTS!

Schedule

The Kolloquium usually takes place on Wednesday at 3pm sharp (German time). Our research group meets in MA 316 to follow the talk. However, several talks may have a hybrid format with an additional Zoom link.

The schedule will be updated regularly.

Planned Talks
Speaker
Title (Format)
Date
Starts
Peter Bürgisser
Integral geometry in nonarchimedean spaces (in person)
06.10.2021
10:15
Peter Bürgisser
Rigid Continuation Paths II: Structured Polynomial Systems (hybrid)
27.10.2021
15:00
Jonathan Leake
Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture (in person)
03.11.2021
15:00
Antonio Lerario
Hausdorff approximation and volume of tubes of singular algebraic sets (hybrid)
10.11.2021
10:15
Gorav Jindal
Efficiently Computing Real Roots of Sparse Polynomials (hybrid)
24.11.2021
15:00
Josué Tonelli-Cueto
What does the condition number of a real polynomial system tell us? Unexpected answers in the real world (hybrid)
07.12.2021
14:15
Amit Sinhababu
Factoring Polynomials given as Arithmetic Branching Programs (hybrid)
15.12.2021
15:00
Dominic Bunnett
Computing cohomology of quotient spaces
12.01.2022
15:00

Abstracts

Integral geometry in nonarchimedean spaces

Speaker: Peter Bürgisser

In a recent paper, Kulkarni and Lerario found a version of Poincare's formula of integral geometry for p-adic projective varieties. (SIAM J. Appl. Alg. Geo, 2021). We extend this result in various directions by developing a conceptual framework over nonarchimedan local fields that mirrors the approach over the reals quite closely. As an application, we obtain precise results on the expected number of p-adic zeros of random fewnomials.
The talk describes ongoing work with Kulkarni and Lerario.

Rigid Continuation Paths II: Structured Polynomial Systems

Speaker: Peter Bürgisser

We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems withprescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most d in n variables with only poly(n,d) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem
This is joint work with Felipe Cucker and Pierre Lairez, see arxiv.org/abs/2010.10997.

Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture

Speaker: Jonathan Leake

About 5 years ago, the Heron-Rota-Welsh conjecture (log-concavity of the coefficients of the reduced characteristic polynomial of a matroid) was proven by Adiprasito, Huh, and Katz via the development of a new combinatorial Hodge theory for matroids. In very recent work with Petter Brändén, we have given a new short "polynomial proof" of the Heron-Rota-Welsh conjecture. Our proof uses an extension of the theory of Lorentzian polynomials to convex cones, and in particular reproves the Hodge-Riemann relations of degree one for the Chow ring of a matroid. In this talk, I will briefly discuss the basics of Lorentzian (aka completely log-concave) polynomials as developed by Anari-Liu-Oveis Gharan-Vinzant and by Brändén-Huh in recent years, and then I will give an overview of our new proof of the Heron-Rota-Welsh conjecture, emphasizing newly developed tools in the theory of Lorentzian polynomials.

Hausdorff approximation and volume of tubes of singular algebraic sets

Speaker: Antonio Lerario

I will discuss the problem of estimating the volume of the tube around an algebraic set (possibly singular) as a function of the dimension of the set and its degree. In particular I will show bounds for the volume of neighborhoods of algebraic sets, in the euclidean space or the sphere, in terms of the degree of the defining polynomials, the number of variables and the dimension of the algebraic set, without any smoothness assumption. This problem is related to numerical algebraic geometry, where sets of ill-contidioned inputs are typically described by (possibly singular) algebraic sets, and their neighborhoods describe bad-conditioned inputs. Our result generalizes previous work of Lotz on smooth complete intersections in the euclidean space and of Bürgisser, Cucker and Lotz on hypersurfaces in the sphere, and gives a complete solution to Problem 17 in the book titled "Condition" by Bürgisser and Cucker.

Efficiently Computing Real Roots of Sparse Polynomials

Speaker: Gorav Jindal

Computing the (real) roots of polynomials is an important problem in mathematics and theoretical computer science. We propose an efficient algorithm to compute the real roots of a sparse polynomial having k non-zero real-valued coefficients. It is known that even for 4-nomials, one can not hope for a polynomial (in the input size) time algorithm for isolating the real roots. Therefore we propose a slightly relaxed notion of isolation of real roots. For a given positive integer L, our algorithm returns disjoint disks D_1,D_2,...,D_s with s < 2k, centered at the real axis and of radius less than 2^{-L} together with positive integers u_1,...,u_s such that each disk D_i contains exactly u_i roots of f counted with multiplicity. In addition, it is ensured that each real root of f is contained in one of the disks. If f has only simple real roots, our algorithm can also be used to isolate all real roots.The bit complexity of our algorithm is polynomial in k and log(n),and near-linear in L and t, where 2^{-t} and 2^t constitute lower and upper bounds on the absolute values of the non-zero coefficients of f, and n is the degree of f. For root isolation, the bit complexity is polynomial in k and log(n), and near-linear in t and log(1/q), where q denotes the separation of the real roots. By using our algorithm, it follows that the real roots of trinomials can be isolated in polynomial time.

This is a joint work with Prof. Michael Sagraloff( Max-Planck-Institut für Informatik and University of Applied Sciences Landshut).

What does the condition number of a real polynomial system tell us? Unexpected answers in the real world

Speaker: Josué Tonelli-Cueto

The condition number of a real polynomial system measures the numerical stability of the system. However, what does this number tell us? In this talk, we will see how this condition number does not control only the numerical stability, but several fundamental algebraic-geometric invariants such as the separation bound and the number of zeros. The latter will have dramatic consequences on the relationship between a polynomial system's number of real zeros and its numerical stability—this phenomenon stands in contrast to the complex setting. This is joint work with Elias Tsigaridas.

Factoring Polynomials given as Arithmetic Branching Programs

Speaker: Amit Sinhababu

A basic problem in computational algebra is polynomial factoring: Given a polynomial, compute all its irreducible factors. In a classic result, Erich Kaltofen proved that if a multivariate polynomial of degree d is given as an arithmetic circuit of size s, then all its factors can be computed by arithmetic circuits of size poly(s,d).In other words, the algebraic complexity class VP is closed under factors. This result has applications in algebraic complexity, for example in derandomization of polynomial identity testing using explicit hard polynomials.
A natural direction to extend Kaltofen's result is to prove analogous factor size bounds in various other models of computing polynomials. Recent works in this area focused on models like constant depth circuits, arithmetic formulas, arithmetic branching programs. Kaltofen's proof does not extend to these models.
In this work, we show poly(s) factor size upper bound for the model of arithmetic branching programs (ABP) using the well-known technique of Hensel lifting. In this talk, I would give a brief survey of the earlier works and present the main ideas of our proof and discuss some of the open questions.

Joint work with Thomas Thierauf, Aalen University.

Computing cohomology of quotient spaces

Speaker: Dominic Bunnett

In this talk we shall give an overview of Kirwan’s method of computing cohomology of quotient spaces. Suppose that we have a reductive group G acting on a projective manifold X. Using the moment map for the action of G on X, one defines a Morse-like function. This Morse-like function allows us to compute topological information of the GIT quotient space X//G. The overview will be example-led and we primarily consider the action of SL_{n+1} on the space of homogenous d-forms, following early work of Kirwan. Time permitting, we will discuss the recent work of [Berczi, Kirwan] and [Hamilton] concerning how one generalises when the group acting is non-reductive. This is the case when considering symmetries of weighted homogenous d-forms (joint work with J. Jackson).

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe