  In this paper we study sums of powers of affine functions in (mostly) one
variable. Although quite simple, this model is a generalization of two
well-studied models: Waring decomposition and sparsest shift. For these three
models there are natural extensions to several variables, but this paper is
mostly focused on univariate polynomials. We present structural results which
compare the expressive power of the three models; and we propose algorithms
that find the smallest decomposition of f in the first model (sums of affine
powers) for an input polynomial f given in dense representation. We also begin
a study of the multivariate case. This work could be extended in several
directions. In particular, just as for Sparsest Shift and Waring decomposition,
one could consider extensions to "supersparse" polynomials and attempt a fuller
study of the multi-variate case. We also point out that the basic univariate
problem studied in the present paper is far from completely solved: our
algorithms all rely on some assumptions for the exponents in an optimal
decomposition, and some algorithms also rely on a distinctness assumption for
the shifts. It would be very interesting to weaken these assumptions, or even
to remove them entirely. Another related and poorly understood issue is that of
the bit size of the constants appearing in an optimal decomposition: is it
always polynomially related to the bit size of the input polynomial given in
dense representation?
