  In this paper, we give a cubic Goldreich-Levin algorithm which makes
polynomially-many queries to a function $f \colon \mathbb F_p^n \to \mathbb C$
and produces a decomposition of $f$ as a sum of cubic phases and a small error
term. This is a natural higher-order generalization of the classical
Goldreich-Levin algorithm. The classical (linear) Goldreich-Levin algorithm has
wide-ranging applications in learning theory, coding theory and the
construction of pseudorandom generators in cryptography, as well as being
closely related to Fourier analysis. Higher-order Goldreich-Levin algorithms on
the other hand involve central problems in higher-order Fourier analysis,
namely the inverse theory of the Gowers $U^k$ norms, which are well-studied in
additive combinatorics. The only known result in this direction prior to this
work is the quadratic Goldreich-Levin theorem, proved by Tulsiani and Wolf in
2011. The main step of their result involves an algorithmic version of the
$U^3$ inverse theorem. More complications appear in the inverse theory of the
$U^4$ and higher norms. Our cubic Goldreich-Levin algorithm is based on
algorithmizing recent work by Gowers and Mili\'cevi\'c who proved new
quantitative bounds for the $U^4$ inverse theorem.
  Our cubic Goldreich-Levin algorithm is constructed from two main tools: an
algorithmic $U^4$ inverse theorem and an arithmetic decomposition result in the
style of the Frieze-Kannan graph regularity lemma. As one application of our
main theorem we solve the problem of self-correction for cubic Reed-Muller
codes beyond the list decoding radius. Additionally we give a purely
combinatorial result: an improvement of the quantitative bounds on the $U^4$
inverse theorem.
