Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-081 | 7th September 2012 09:17

An exponential lower bound for the sum of powers of bounded degree polynomials

RSS-Feed




Revision #1
Authors: Neeraj Kayal
Accepted on: 7th September 2012 09:17
Downloads: 4194
Keywords: 


Abstract:

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of degree at most $d$. We give an explicit $n$-variate polynomial $f$ of degree $n$ such that any representation of the above form for $f$ requires the number of summands $s$ to be $2^{\Omega(n/d)}$.



Changes to previous version:

The lower bound has been improved and it now asymptotically matches the upper bound. Some other relevant references have been added.


Paper:

TR12-081 | 26th June 2012 10:25

An exponential lower bound for the sum of powers of bounded degree polynomials





TR12-081
Authors: Neeraj Kayal
Publication: 26th June 2012 14:40
Downloads: 4603
Keywords: 


Abstract:

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit $n$-variate polynomial $f$ of degree $n$ such that any representation of the above form for $f$ requires the number of summands $s$ to be $2^{\Omega(n)}$.



ISSN 1433-8092 | Imprint