BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Sayantan Chakraborty (TIFR\, Mumbai)
DTSTART:20210906T090000Z
DTEND:20210906T110000Z
DTSTAMP:20260421T174136Z
UID:BPS/35
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BPS/35/">Imp
 roved Bounds for Perfect Sampling of k-Colorings in Graphs.</a>\nby Sayant
 an Chakraborty (TIFR\, Mumbai) as part of Bangalore Probability Seminar\n\
 n\nAbstract\nI this talk we will present a randomized algorithm that takes
  as input an undirected n-vertex graph G with maximum degree Δ and an int
 eger k>3Δ\, and returns a random proper k-coloring of G. The distribution
  of the coloring is \\emph{perfectly} uniform over the set of all proper k
 -colorings\; the expected running time of the algorithm is poly(k\,n)=O(n
 Δ^2⋅log(k)). This improves upon a result of Huber~(STOC 1998) who obtai
 ned a polynomial time perfect sampling algorithm for k>Δ^2+2Δ. Prior to 
 our work\, no algorithm with expected running time poly(k\,n) was known to
  guarantee perfectly sampling with sub-quadratic number of colors in gener
 al. Our algorithm (like several other perfect sampling algorithms includin
 g Huber's) is based on the Coupling from the Past method. Inspired by the 
 \\emph{bounding chain} approach\, pioneered independently by Huber~(STOC 1
 998) and Häggström & Nelander~(Scand. J. Statist.\, 1999)\, we employ a 
 novel bounding chain to derive our result for the graph coloring problem.\
 n
LOCATION:https://researchseminars.org/talk/BPS/35/
END:VEVENT
END:VCALENDAR