  We present a new parallel algorithm for $k$-clique counting/listing that has
polylogarithmic span (parallel time) and is work-efficient (matches the work of
the best sequential algorithm) for sparse graphs. Our algorithm is based on
computing low out-degree orientations, which we present new linear-work and
polylogarithmic-span algorithms for computing in parallel. We also present new
parallel algorithms for producing unbiased estimations of clique counts using
graph sparsification. Finally, we design two new parallel work-efficient
algorithms for approximating the $k$-clique densest subgraph, the first of
which is a $1/k$-approximation and the second of which is a
$1/(k(1+\epsilon))$-approximation and has polylogarithmic span. Our first
algorithm does not have polylogarithmic span, but we prove that it solves a
P-complete problem.
  In addition to the theoretical results, we also implement the algorithms and
propose various optimizations to improve their practical performance. On a
30-core machine with two-way hyper-threading, our algorithms achieve
13.23--38.99x and 1.19--13.76x self-relative parallel speedup for $k$-clique
counting and $k$-clique densest subgraph, respectively. Compared to the
state-of-the-art parallel $k$-clique counting algorithms, we achieve up to
9.88x speedup, and compared to existing implementations of $k$-clique densest
subgraph, we achieve up to 11.83x speedup. We are able to compute the
$4$-clique counts on the largest publicly-available graph with over two hundred
billion edges for the first time.
