  We present a randomized $O(m \log^2 n)$ work, $O(\text{polylog } n)$ depth
parallel algorithm for minimum cut. This algorithm matches the work bounds of a
recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP'20], and
improves on the previously best parallel algorithm by Geissmann and Gianinazzi
[SPAA'18], which performs $O(m \log^4 n)$ work in $O(\text{polylog } n)$ depth.
  Our algorithm makes use of three components that might be of independent
interest. Firstly, we design a parallel data structure that efficiently
supports batched mixed queries and updates on trees. It generalizes and
improves the work bounds of a previous data structure of Geissmann and
Gianinazzi and is work efficient with respect to the best sequential algorithm.
Secondly, we design a parallel algorithm for approximate minimum cut that
improves on previous results by Karger and Motwani. We use this algorithm to
give a work-efficient procedure to produce a tree packing, as in Karger's
sequential algorithm for minimum cuts. Lastly, we design an efficient parallel
algorithm for solving the minimum $2$-respecting cut problem.
