Computing the Three-Point Correlation Function of Galaxies in
  $\mathcal{O}(N^2)$ Time
  We present an algorithm that computes the multipole coefficients of the
galaxy three-point correlation function (3PCF) without explicitly considering
triplets of galaxies. Rather, centering on each galaxy in the survey, it
expands the radially-binned density field in spherical harmonics and combines
these to form the multipoles without ever requiring the relative angle between
a pair about the central. This approach scales with number and number density
in the same way as the two-point correlation function, allowing runtimes that
are comparable, and 500 times faster than a naive triplet count. It is exact in
angle and easily handles edge correction. We demonstrate the algorithm on the
LasDamas SDSS-DR7 mock catalogs, computing an edge corrected 3PCF out to
$90\;{\rm Mpc}/h$ in under an hour on modest computing resources. We expect
this algorithm will render it possible to obtain the large-scale 3PCF for
upcoming surveys such as Euclid, LSST, and DESI.
