Name
Abstract | ||
|---|---|---|
One question that we investigate in this paper is, how can we build log-concave polynomials using sparse polynomials as building blocks? More precisely, let f = Sigma(d)(i=0) a(i),X-i E R+[X] be a polynomial satisfying the log-concavity condition a(i)(2), > Ta-i-1a(i),,+1 for every i is an element of {1,,d 1}, where r > 0. Whenever f can be written under the form f = Sigma(k)(i) = 1 Pi(m)(j)=1 f(i,j) where the polynomials fi have at most t monomials, it is clear that d ktm. Assuming that the have only non-negative coefficients, we improve this degree bound to d = O(km(2/3)t(2m/3)log(2/3) (kt)) if T > 1, and to d kmt if T = d(2d) This investigation has a complexity-theoretic motivation: we show that a suitable strengthening of the above results would imply a separation of the algebraic complexity classes VP and VNP. As they currently stand, these results are strong enough to provide a new example of a family of polynomials in VN P which cannot be computed by monotone arithmetic circuits of polynomial size. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48054-0_30 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Discrete mathematics,Arithmetic circuits,Combinatorics,Newton polygon,Polynomial,Monomial,Mathematics,Bivariate polynomials | Journal | 9235 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ignacio García-Marco | 1 | 6 | 2.66 |
| Pascal Koiran | 2 | 919 | 113.85 |
| Sébastien Tavenas | 3 | 14 | 5.19 |