A tau-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 ''tau-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 tau-conjecture.'' Finally, we make some progress toward the tau-conjecture for Newton polygons using recent results from combinatorial geometry.
Type de document :
Rapport
2014, pp.14
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00850791
Contributeur : Pascal Koiran <>
Soumis le : lundi 12 mai 2014 - 20:51:02
Dernière modification le : mardi 24 avril 2018 - 13:52:21
Document(s) archivé(s) le : mardi 12 août 2014 - 12:20:30

Fichiers

newton.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00850791, version 2
  • ARXIV : 1308.2286

Collections

Citation

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé. A tau-conjecture for Newton polygons. 2014, pp.14. 〈ensl-00850791v2〉

Partager

Métriques

Consultations de la notice

202

Téléchargements de fichiers

136