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
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
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.