Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set

DOI10.1145/3326171MaRDI QIDQ4972690zbMATH OpenOpenAlexWikidataFDO

Authors David G. Harris

Publication date 25 November 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.06156

zbMATH Keywords

concentration boundshypergraphmaximal independent setMIS

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: 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). The best randomized parallel algorithm for hypergraphs of fixed rank $r$ was developed by Beame & Luby (1990) and Kelsen (1992), running in time roughly $(logn{)}^{r!}$. We improve the randomized algorithm of Kelsen, reducing the runtime to roughly $(logn{)}^{2^r}$ 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 $(logn{)}^{2^{r+3}}$ time and $extpoly(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(fraclog(mn)loglog(mn)))$.

Recommendations

• Derandomized concentration bounds for polynomials, and hypergraph maximal independent set
• On the concentration of the independence numbers of random hypergraphs
• Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs
• scientific article; zbMATH DE number 1222591
• On the maximal independence polynomial of certain graph configurations
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• Anti-concentration for polynomials of independent random variables
• Concentration and moment inequalities for polynomials of independent random variables

Cites work

• A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
• A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Algorithmic derandomization via complexity theory
• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• Concentration and moment inequalities for polynomials of independent random variables
• Concentration of multivariate polynomials and its applications
• Concentration of non‐Lipschitz functions and applications
• scientific article; zbMATH DE number 432767 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Improved parallel approximation of a class of integer programming problems
• On the concentration of multivariate polynomials with small expectation
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• The complexity of parallel search
• Tight analysis of parallel randomized greedy MIS

Cited in

(5)

• Approximation in (poly-) logarithmic space
• Derandomized concentration bounds for polynomials, and hypergraph maximal independent set
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• LATIN 2004: Theoretical Informatics
• Distributed coloring of hypergraphs

This page was built for publication: Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972690)