Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
复制标题
多项式的去随机浓度界限和超图最大独立集
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
David G. Harris
中科院分区：
文献类型：
--
作者：
David G. Harris
超图中极大独立集（MIS）的并行算法一直是一个长期存在的算法挑战，可以追溯到近30年前Karp和Ramachandran（1990）的调查。Beame和吕比（1990）和Kelsen（1992）提出了固定秩r超图的最佳随机并行算法，运行时间大约为（log n）r！。我们改进了Kelsen的随机算法，将运行时间减少到大约（log n）2 r，并通过使用更现代的浓度不等式简化了分析。我们还给出了一种低次多项式浓度界的去随机化方法，这是分析该算法的关键技术工具。这导致确定性PRAM算法也在（log n）2 r +3时间和poly（m，n）处理器中运行。这是第一个确定性算法与子多项式运行时间的超图秩r > 3。当r缓慢增长时，我们的分析也适用;将其与Bercea et al.（2015）的策略结合使用，给出了在时间exp（O（log（mn）/ log log（mn））中运行的确定性MIS算法。
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!. We improve the randomized algorithm of Kelsen, reducing the runtime to roughly (log n)2r and simplifying the analysis through the use of more-modern concentration inequalities. We also give a method for derandomizing concentration bounds for low-degree polynomials, which are the key technical tool used to analyze that algorithm. This leads to a deterministic PRAM algorithm also running in (log n)2r+3 time and poly(m,n) processors. This is the first deterministic algorithm with sub-polynomial runtime for hypergraphs of rank r > 3. 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 (mn) / log log (mn)).