Analysis of the parallel peeling algorithm: a short proof

Abstract

A recent paper by Jiang, Mitzenmacher and Thaler upper bounded the number of rounds needed in a parallel peeling algorithm applied to a random hypergraph whose edge density is below the k-core emergence threshold. I gave a very short proof of their result in this note.

References in corpus (1)

• Parallel Peeling Algorithms

Cited by in corpus (3)

• The stripping process can be slow: part I
• Parallel Peeling Algorithms
• Sandwiching random regular graphs between binomial random graphs