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 & Ramachandran (1990). Despite its apparent simplicity, there have been no general sub-polynomial-time algorithms or hardness reductions. The best randomized parallel algorithm for hypergraphs of fixed rank r was developed by Beame & Luby (1990) and Kelsen (1992), running in time roughly (log n)~(r!). The key probabilistic tool underlying this algorithm is a concentration bound for low-degree polynomials applied to independent input variables; this is a natural generalization of concentration bounds for sums of independent random variables, which are ubiquitous in combinatorics and computer science. These concentration bounds for polynomials do not lend themselves to standard derandomization techniques. Thus, the algorithm of Kelsen cannot be derandomized in any known way. There are no deterministic parallel algorithms for hypergraph MIS for any fixed rank r > 3. We improve the randomized algorithm of Kelsen to obtain a running time of (log n)~(2~r). We also give a method for derandomizing concentration bounds for polynomials, thus obtaining a deterministic algorithm running in (log n)~(2~(r+3)) time and (mn)~(O(1)) processors. Our analysis can also apply when r is slowly growing; using this in conjunction with a strategy of Bercea et al. (2015) gives a deterministic MIS algorithm running in time exp(O(log m/log log m + log log n).