  We present the first parallel depth-first search algorithm for undirected
graphs that has near-linear work and sublinear depth. Concretely, in any
$n$-node $m$-edge undirected graph, our algorithm computes a DFS in
$\tilde{O}(\sqrt{n})$ depth and using $\tilde{O}(m+n)$ work. All prior work
either required $\Omega(n)$ depth, and thus were essentially sequential, or
needed a high $poly(n)$ work and thus were far from being work-efficient.
