Counting Hypergraph Colorings in the Local Lemma Regime
From MaRDI portal
Publication:5232330
DOI10.1137/18M1202955zbMath1430.68447arXiv1711.03396OpenAlexW2966749622WikidataQ124799475 ScholiaQ124799475MaRDI QIDQ5232330
Chihao Zhang, Heng Guo, Pinyan Lu, Chao Liao
Publication date: 2 September 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.03396
Hypergraphs (05C65) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- On a packing and covering problem
- Random generation of combinatorial structures from a uniform distribution
- Asymptotic lower bounds for Ramsey functions
- Randomly coloring simple hypergraphs
- Randomly coloring simple hypergraphs with fewer colors
- Improved bounds for sampling colorings
- Improved FPTAS for Multi-spin Systems
- Randomly coloring constant degree graphs
- Counting independent sets up to the tree threshold
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Polynomial-Time Approximation Algorithms for the Ising Model
- Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
- Random Walks That Find Perfect Objects and the Lovász Local Lemma
- Path coupling using stopping times and counting independent sets and colorings in hypergraphs
- A constructive proof of the general lovász local lemma
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Stopping Times, Metrics and Approximate Counting
- How to Generate Factored Random Numbers
- A parallel algorithmic version of the local lemma
- A random polynomial-time algorithm for approximating the volume of convex bodies
- An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
- Approximation via Correlation Decay When Strong Spatial Mixing Fails
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Left and right convergence of graphs with bounded degree
- Rapid mixing of hypergraph independent sets
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Improved Bounds for Randomly Sampling Colorings via Linear Programming
- Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
- Uniform Sampling Through the Lovász Local Lemma
- New Constructive Aspects of the Lovász Local Lemma
- Constraint satisfaction, packet routing, and the lovasz local lemma
- Distributed algorithms for the Lovász local lemma and graph coloring
This page was built for publication: Counting Hypergraph Colorings in the Local Lemma Regime
