TU Berlin

Fachgebiet Algorithmische AlgebraKolloquium (Oberseminar)

Inhalt des Dokuments

zur Navigation

Kolloquium

In unserem Kolloquium algorithmische Mathematik und Komplexitätstheorie tragen Mitarbeiter und Gäste über aktuelle Themen ihrer Forschung vor.

In our Kolloquium on algorithmic mathematics and complexity theory, guests and members of the group presents current topics about their research. 

Terminplan

Geplante Vorträge
Vortragender
Titel
Datum
Zeit
Grigoris Paouris
The "Small ball" property in high dimensional measures*
24.05.2018
1615-1745
Pranjal Dutta
Discovering the roots: Uniform closure results for algebraic classes under factoring
31.05.2018
1415-1545
Peter Bürgisser
The Real Tau-Conjecture is true on average
14.06.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1415-1545
YY.XX.2018
1515-1645

Abstracts

The "Small ball" property in high dimensional measures*

*This talk will take place inside the Seminar der Arbeitsgruppen Diskrete Mathematik in room MA313.

Speaker: Grigoris Paouris (Texas A&M University)

I will discuss some methods/techniques to prove "small ball probabilities" and I will review some connections with other problems in Asymptotic Geometric Analysis. The emphasis will be on how high-dimensional geometry and convexity is crucial to understand the concentration behavior in the "small ball regime".

Discovering the roots: Uniform closure results for algebraic classes under factoring

Speaker: Pranjal Dutta (Chennai Mathematical Institute)

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. I will talk about generalizing it to a matrix recurrence that approximates all the roots "simultaneously". I will also discuss an interesting property of multivariate polynomial factorization which shows that under a random linear transformation ? , f (?x) completely factors via power series roots. Combining these, I will establish that for an algebraic circuit f(x_1 , ? , x_n ) of size s , each factor has size at most a polynomial in: s and the degree of the square-free part of f . For the remaining time, I will talk about different model of interest when the given polynomial f is of degree poly(n) and can be computed by a formula (resp. Algebraic Branching Program) size poly(n^{log n) . I will show how to find a similar size formula (resp. ABP) factor in randomized poly(n^{log n}) -time.

This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur), STOC?18.

The Real Tau-Conjecture is true on average

Speaker: Peter Bürgisser (TU Berlin)

Koiran's real tau-conjecture claims that the number of real zeros of a structured polynomial given as a sum of m products of k real sparse polynomials, each with at most t monomials, is bounded by a polynomial in m, k, t. This conjecture has a major consequence in complexity theory since it would lead to superpolynomial bounds for the arithmetic circuit size of the permanent. We confirm the conjecture in a probabilistic sense by proving that if the coefficients involved in the description of  f are independent standard Gaussian randomvariables, then the expected number of real zeros of f is O(mkt), which is linear in the number of parameters.

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

TBA

Speaker: TBA

TBA

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe