Counting Hypergraph Colourings in the Local Lemma Regime

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of q-colorings for k-uniform hypergraphs with maximum degree Δ if k≥ 28 and q > 315Δ14/k−14. We also obtain a polynomial-time almost uniform sampler if q>798Δ16/k−16/3. These are the first approximate counting and sampling algorithms in the regime q≪Δ (for large Δ 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 Δ in Moitra’s approach.
Original languageEnglish
Title of host publicationProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Place of PublicationNew York, NY, USA
PublisherACM
Pages926-939
Number of pages14
ISBN (Print)978-1-4503-5559-9
DOIs
Publication statusPublished - 29 Jun 2018
Event50th Annual ACM Symposium on the Theory of Computing - Los Angeles, United States
Duration: 25 Jun 201829 Jun 2018
http://acm-stoc.org/stoc2018/

Publication series

NameSTOC 2018
PublisherACM

Conference

Conference50th Annual ACM Symposium on the Theory of Computing
Abbreviated titleSTOC 2018
Country/TerritoryUnited States
CityLos Angeles
Period25/06/1829/06/18
Internet address

Keywords / Materials (for Non-textual outputs)

  • Approximate Counting
  • Lovász Local Lemma

Fingerprint

Dive into the research topics of 'Counting Hypergraph Colourings in the Local Lemma Regime'. Together they form a unique fingerprint.

Cite this