Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
From MaRDI portal
Publication:4972690
DOI10.1145/3326171zbMath1455.68272arXiv1609.06156OpenAlexW2960354271WikidataQ127495031 ScholiaQ127495031MaRDI QIDQ4972690
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
Analysis of algorithms (68W40) Hypergraphs (05C65) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)
Related Items (3)
Distributed coloring of hypergraphs ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Approximation in (Poly-) logarithmic space
Cites Work
- Improved parallel approximation of a class of integer programming problems
- The complexity of parallel search
- An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
- A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Algorithmic derandomization via complexity theory
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
- On the concentration of multivariate polynomials with small expectation
- Concentration of non‐Lipschitz functions and applications
- Concentration and Moment Inequalities for Polynomials of Independent Random Variables
- Concentration of multivariate polynomials and its applications
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
