  We present improved distributed algorithms for triangle detection and its
variants in the CONGEST model. We show that Triangle Detection, Counting, and
Enumeration can be solved in $\tilde{O}(n^{1/2})$ rounds. In contrast, the
previous state-of-the-art bounds for Triangle Detection and Enumeration were
$\tilde{O}(n^{2/3})$ and $\tilde{O}(n^{3/4})$, respectively, due to Izumi and
LeGall (PODC 2017).
  The main technical novelty in this work is a distributed graph partitioning
algorithm. We show that in $\tilde{O}(n^{1-\delta})$ rounds we can partition
the edge set of the network $G=(V,E)$ into three parts $E=E_m\cup E_s\cup E_r$
such that
  (a) Each connected component induced by $E_m$ has minimum degree
$\Omega(n^\delta)$ and conductance $\Omega(1/\text{poly} \log(n))$. As a
consequence the mixing time of a random walk within the component is
$O(\text{poly} \log(n))$.
  (b) The subgraph induced by $E_s$ has arboricity at most $n^{\delta}$.
  (c) $|E_r| \leq |E|/6$.
  All of our algorithms are based on the following generic framework, which we
believe is of interest beyond this work. Roughly, we deal with the set $E_s$ by
an algorithm that is efficient for low-arboricity graphs, and deal with the set
$E_r$ using recursive calls. For each connected component induced by $E_m$, we
are able to simulate congested clique algorithms with small overhead by
applying a routing algorithm due to Ghaffari, Kuhn, and Su (PODC 2017) for high
conductance graphs.
