#
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

*Abstract:*

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 X^{i} Y^{j}
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

*Abstract:*

Let f(x) be a polynomial with k non-zero real coefficients. What is the minimum number N_{k} 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 N_{k} 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