[Theory] 3/24 Talks at TTIC: Siddharth Bhandari, Tata Institute of Fundamental Research

[Mary Marre]

*When:*      Wednesday, March 24th at* 11:10 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_cxTpN_kyT2WC_2F8fNWj2g>*)



*Who: *       Siddharth Bhandari, Tata Institute of Fundamental Research,
India


*Title:*        Sandwich to Sample Exactly

*Abstract:* In this talk, we will look at recent progress on "exact
sampling" of two central problems: Graph Colorings and Independent Sets.
The classical algorithms for approximately sampling from the corresponding
Gibb's Distribution involve running the appropriate Glauber Dynamics (GD)
for a fixed amount of time depending on the input size and outputting a
sample whose distribution is close to the corresponding Gibb's
Distribution. The quantity of interest then, is the mixing time of the GD
which quantifies how fast the chain converges to the stationary
distribution starting from an arbitrary initial configuration.

However, the above algorithms only produce approximate samples. Thus, it is
natural to ask if we can efficiently produce a sample that is distributed
exactly according to the Gibb's Distribution. Apart from its independent
theoretical appeal, exact sampling algorithms potentially yield faster
FPRASs and provide exact samples even in the absence of guarantees on the
mixing time.

The intriguing fact that exact sampling is in general possible using Markov
Chains was established by Propp and Wilson'96 in a seminal work which
introduced the technique of Coupling from the Past (CFTP). This, coupled
with the Bounding Chain technique of Huber'98, and Haggstrom & Nelander'99,
lets us use the GD to efficiently sample exactly from the Gibb's
Distribution for the case of colorings and independent sets, however, for a
much-restricted set of parameters as compared to the approximate sampling
counterparts. We will see how to bridge this gap between approximate and
exact sampling for these fundamental problems.

*Host:* Madhur Tulsiani <madhurt at ttic.edu>




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210319/10ca0038/attachment.html>