ECCC-Report TR12-081https://eccc.weizmann.ac.il/report/2012/081Comments and Revisions published for TR12-081en-usFri, 07 Sep 2012 09:17:17 +0300
Revision 1
| An exponential lower bound for the sum of powers of bounded degree polynomials |
Neeraj Kayal
https://eccc.weizmann.ac.il/report/2012/081#revision1In 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)}$.Fri, 07 Sep 2012 09:17:17 +0300https://eccc.weizmann.ac.il/report/2012/081#revision1
Paper TR12-081
| An exponential lower bound for the sum of powers of bounded degree polynomials |
Neeraj Kayal
https://eccc.weizmann.ac.il/report/2012/081In 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)}$.Tue, 26 Jun 2012 14:40:21 +0300https://eccc.weizmann.ac.il/report/2012/081