通知公告
通知公告
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

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