Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set

摘要

A parallel algorithm for maximal independent set (MIS) in hypergraphs has been a long-standing algorithmic challenge, dating back nearly 30 years to a survey of Karp and Ramachandran (1990). The best randomized parallel algorithm for hypergraphs of fixed rank r was developed by Beame and Luby (1990) and Kelsen (1992), running in time roughly (log n)(r!).