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) for writing an explicit univariate degree d polynomial f(x) as a sum of powers of degree-t polynomials.
Joint work with Neeraj Kayal, Timothée Pecatte and Chandan Saha.