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