The analysis of several algorithms and data structures can be framed as a peeling

process on a random hypergraph: vertices with degree less than *k* are removed

until there are no vertices of degree less than *k* left. The remaining hypergraph

is known as the *k*-core. In this paper, we analyze parallel peeling processes,

where in each round, all vertices of degree less than *k* are removed. It is

known that, below a specific edge density threshold, the *k*-core is empty

with high probability. We show that, with high probability, below this threshold,

only *1 / log((k-1)(r-1)) log log n + O(1)* rounds of peeling are needed to obtain

the empty *k*-core for *r*-uniform hypergraphs. Interestingly, we show

that above this threshold, *Ω(log n)* rounds of peeling are required to find the non-empty

*k*-core. Since most algorithms and data structures aim to peel to an empty *k*-core,

this asymmetry appears fortunate. We verify the theoretical results both with simulation

and with a parallel implementation using graphics processing units (GPUs). Our

implementation provides insights into how to structure parallel peeling algorithms

for efficiency in practice.

**Guest**: Michael Mitzenmacher

**Host:**Stefan Schmid

Podcast: Play in new window | Download