CS Peer Talks

Inapproximability of Counting Hypergraph Colourings

  • Jiaheng Wang, University of Edinburgh
  • Time: 2022-05-11 19:00
  • Host: Turing Class Research Committee
  • Venue: Online Talk


We separate the computational threshold between the searching and approximate counting version of hypergraph colourings in the Lovász local lemma regime. To be more precise, approximately counting the number of proper q-colourings of a K-uniform hypergraph with maximum degree D is NP-hard whenever D is greater than 5q^{K/2} and q is an even number greater or equal than 4, while the searching problem remains tractable till D reaches roughly q^K.



Jiaheng Wang is a second-year PhD student at the School of Informatics, University of Edinburgh. He has a general interest in theory of computing, especially those involving randomness and combinatorial structures.


  • Admission


Tencent ID: 1500-613-467

Passcode: 202257