Lower Bounds for Sums of Powers of Low Degree Univariates

摘要

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Ω((d/t)~(1/2)) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.