Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 18, 2013

Technische Universität Berlin
Institut für Mathematik
Straße des 17. juni 136
10623 Berlin Berlin
room MA 041

Lecture - 14:15

Pascal Koiran - Ecole Normale Supérieure de Lyon

A τ-conjecture for Newton polygons

One can associate to any bivariate polynomial P(X,Y) its Newton polygon. This is the convex hull of the points (i,j) such that the monomial Xi Yj appears in P with a nonzero coefficient.
We conjecture that when P is expressed as a sum of products of sparse polynomials, the number of edges of its Newton polygon is polynomially bounded in the size of such an expression. We show that this ``τ-conjecture for Newton polygons,'' even in a weak form, implies that the permanent polynomial is not computable by polynomial size arithmetic circuits. We make the same observation for a weak version of an earlier ``real τ-conjecture.'' Finally, we make some progress toward the τ-conjecture for Newton polygons using recent results from combinatorial geometry.

This talk is based on joint work with Natacha Portier, Sébastien Tavenas and Stéphan Thomassé. I will present our results and conjectures, starting from the very basic properties of Newton polygons (and in particular the role of Minkowski sum).

Colloquium - 16:00

Codrut Grosu - Berlin

On sparse polynomial powers and related questions

Let f(x) be a polynomial with k non-zero real coefficients. What is the minimum number Nk of non-zero terms the polynomial f(x)2 can have? This question goes back to Rényi and has been studied throughout the years by various authors, albeit the asymptotic behaviour of Nk is still unknown.

It is less known that Rényi also asked if it makes any difference if f(x) has rational, real or complex coefficients. I shall present some progress on this question, and also explain how this topic relates to some questions in additive combinatorics.

Letzte Aktualisierung: 11.11.2013