  Given nonnegative integers $n$ and $d$, where $n \gg d$, what is the minimum
number $r$ such that there exist linear forms $\ell_1, \ldots, \ell_r \in
\mathbb{C}[x_1, \ldots, x_n]$ so that $\ell_1^d + \cdots + \ell_r^d$ is
supported exactly on the set of all degree-$d$ multilinear monomials in $x_1,
\ldots, x_n$? We show that this and related questions have surprising and
intimate connections to the areas of parameterized and exact algorithms,
generalizing several well-known methods and providing a concrete approach to
obtain faster approximate counting and deterministic decision algorithms. This
gives a new application of Waring rank, a classical topic in algebraic geometry
with connections to algebraic complexity theory, to computer science.
  To illustrate the amenability and utility of this approach, we give a
randomized $4.075^d \cdot \mathrm{poly}(n, \varepsilon^{-1})$-time algorithm
for computing a $(1 + \varepsilon)$ approximation of the sum of the
coefficients of the multilinear monomials in a degree-$d$ homogeneous
$n$-variate polynomial with nonnegative coefficients. As an application of this
we give a faster algorithm for approximately counting subgraphs of bounded
treewidth, improving on earlier work of Alon et al. Along the way we give an
exact answer to an open problem of Koutis and Williams and sharpen a lower
bound on the size of perfectly balanced hash families given by Alon and Gutner.
