Name
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. |
Year | Venue | Field |
|---|---|---|
2013 | Foundations of Computational Mathematics | Discrete geometry,Polygon,Mathematical optimization,Newton polygon,Combinatorics,Polynomial,Mathematical analysis,Convex hull,Monomial,Arithmetic circuit complexity,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1308.2286 | 0 |
PageRank | References | Authors |
0.34 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Koiran | 1 | 919 | 113.85 |
| Natacha Portier | 2 | 96 | 11.49 |
| Sébastien Tavenas | 3 | 14 | 5.19 |
| Stéphan Thomassé | 4 | 651 | 66.03 |