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 Ω({the square root of}(d/t)) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.