AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Expert Audience

English

60 Minutes

Saarbrücken

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

Markus Bläser

--email hidden

passcode not visible

logged in users only