Learning sums of powers of low-degree polynomials in the non-degenerate
  case
  We develop algorithms for writing a polynomial as sums of powers of low
degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can
be written as $$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$ where each $c_i\in
\mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m
= d$. In this paper, we give a $\text{poly}((ns)^t)$-time learning algorithm
for finding the $Q_i$'s given (black-box access to) $f$, if the $Q_i's$ satisfy
certain non-degeneracy conditions and $n$ is larger than $d^2$. The set of
degenerate $Q_i$'s (i.e., inputs for which the algorithm does not work) form a
non-trivial variety and hence if the $Q_i$'s are chosen according to any
reasonable (full-dimensional) distribution, then they are non-degenerate with
high probability (if $s$ is not too large).
  Our algorithm is based on a scheme for obtaining a learning algorithm for an
arithmetic circuit model from a lower bound for the same model, provided
certain non-degeneracy conditions hold. The scheme reduces the learning problem
to the problem of decomposing two vector spaces under the action of a set of
linear operators, where the spaces and the operators are derived from the input
circuit and the complexity measure used in a typical lower bound proof. The
non-degeneracy conditions are certain restrictions on how the spaces decompose.
