[Theory] NOW: 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.

In particular, for sampling colorings, our work (Bhandari and Chakraborty)
makes the exact sampling requirement on the number of colors from quadratic
in the maximum degree of the graph to linear: hence, we make exact
sampling comparable to the best approximate sampling results.  For the case
of independent sets, we (Bhandari, Chakraborty and Srivastava) show an
efficient exact sampling algorithm all the way till the tree uniqueness
threshold for graphs with large girth and degrees at least logarithmic in
the number of vertices: this is a common setting for the various results in
the approximate sampling paradigm. Prior to this work no results were known
where 'local-uniformity' techniques for proving fast mixing of chains were
lifted to exact sampling.

*Bio: * Siddharth Bhandari is a fifth year graduate student in the School
of Technology and Computer Science at the Tata Institute of Fundamental
Research, Mumbai. Siddharth is pursuing his Ph.D. under the guidance of
Prof. Prahladh Harsha. Previously, he obtained a B.Tech.degree in
Mechanical Engineering from IIT, Kharagpur and a M.Sc. degree in Computer
Science from CMI.

His research interests lie broadly in the field of randomized computation.
He has dabbled in zero-error information theory, coding theory, sampling
algorithms and theoretical guarantees for generative networks. Website:
https://sites.google.com/view/siddharth-bhandari/home


*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>*


On Wed, Mar 24, 2021 at 10:00 AM Mary Marre <mmarre at ttic.edu> wrote:

> *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.
>
> In particular, for sampling colorings, our work (Bhandari and Chakraborty)
> makes the exact sampling requirement on the number of colors from quadratic
> in the maximum degree of the graph to linear: hence, we make exact
> sampling comparable to the best approximate sampling results.  For the case
> of independent sets, we (Bhandari, Chakraborty and Srivastava) show an
> efficient exact sampling algorithm all the way till the tree uniqueness
> threshold for graphs with large girth and degrees at least logarithmic in
> the number of vertices: this is a common setting for the various results in
> the approximate sampling paradigm. Prior to this work no results were known
> where 'local-uniformity' techniques for proving fast mixing of chains were
> lifted to exact sampling.
>
> *Bio: * Siddharth Bhandari is a fifth year graduate student in the School
> of Technology and Computer Science at the Tata Institute of Fundamental
> Research, Mumbai. Siddharth is pursuing his Ph.D. under the guidance of
> Prof. Prahladh Harsha. Previously, he obtained a B.Tech.degree in
> Mechanical Engineering from IIT, Kharagpur and a M.Sc. degree in Computer
> Science from CMI.
>
> His research interests lie broadly in the field of randomized computation.
> He has dabbled in zero-error information theory, coding theory, sampling
> algorithms and theoretical guarantees for generative networks. Website:
> https://sites.google.com/view/siddharth-bhandari/home
>
>
> *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>*
>
>
> On Tue, Mar 23, 2021 at 5:06 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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.
>>
>> In particular, for sampling colorings, our work (Bhandari and
>> Chakraborty) makes the exact sampling requirement on the number of colors
>> from quadratic in the maximum degree of the graph to linear: hence, we make
>> exact sampling comparable to the best approximate sampling results.  For
>> the case of independent sets, we (Bhandari, Chakraborty and Srivastava)
>> show an efficient exact sampling algorithm all the way till the tree
>> uniqueness threshold for graphs with large girth and degrees at least
>> logarithmic in the number of vertices: this is a common setting for the
>> various results in the approximate sampling paradigm. Prior to this work no
>> results were known where 'local-uniformity' techniques for proving fast
>> mixing of chains were lifted to exact sampling.
>>
>> *Bio: * Siddharth Bhandari is a fifth year graduate student in the
>> School of Technology and Computer Science at the Tata Institute of
>> Fundamental Research, Mumbai. Siddharth is pursuing his Ph.D. under the
>> guidance of Prof. Prahladh Harsha. Previously, he obtained a B.Tech.degree
>> in Mechanical Engineering from IIT, Kharagpur and a M.Sc. degree in
>> Computer Science from CMI.
>>
>> His research interests lie broadly in the field of randomized
>> computation. He has dabbled in zero-error information theory, coding
>> theory, sampling algorithms and theoretical guarantees for generative
>> networks. Website: https://sites.google.com/view/siddharth-bhandari/home
>>
>>
>> *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>*
>>
>>
>> On Fri, Mar 19, 2021 at 2:37 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *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/20210324/f1ea823c/attachment-0001.html>