BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability seminar
SUMMARY:Counting hypergraph colorings in the local lemma r
egime - Heng Guo (University of Edinburgh)
DTSTART:20190131T130000Z
DTEND:20190131T140000Z
UID:TALK3492AT
URL:/talk/index/3492
DESCRIPTION:I will present a fully polynomial-time approximati
on scheme (FPTAS) to count the number of q-colorin
gs for k-uniform hypergraphs with maximum degree D
if k>=28 and q>315D^{14/(k−14)}\, as well as an a
ccompanying sampling algorithm with slightly worse
conditions. These are the first approximate count
ing and sampling algorithms in the regime q\\ll Δ
(for large Δ and k) without any additional assumpt
ions. In these regimes\, frozen colourings are pre
sent\, forming an obstacle to the standard Markov
chain Monte Carlo approach. Instead\, our method i
s based on the recent work of Moitra (STOC\, 2017)
\, in which Lovasz Local Lemma is the key ingredie
nt. \n\nJoint work with Chao Liao\, Pinyan Lu\, Ch
ihao Zhang
LOCATION:Watson LTB
CONTACT:Richard Montgomery
END:VEVENT
END:VCALENDAR