# Counting hypergraph colorings in the local lemma regime

arXiv: https://arxiv.org/abs/1711.03396 · HTML: https://mlsanity.com/paper/1711.03396/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2017.

## Built on by (most cited first, 1 of 1)

- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of q-colorings for k-uniform hypergraphs with maximum degree Delta if k≥ 28 and q >357Delta^frac14k-14 . We also obtain a polynomial-time almost uniform sampler if q>931Delta^frac16k-16/3. These are the first approximate counting and sampling algorithms in the regime qllDelta (for large Delta and k) without any additional assumptions. Our method is based on the recent work of Moitra (STOC, 2017). One important contribution of ours is to remove the dependency of k and Delta in Moitra's approach.