Abstract

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.

Biography

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