Skip to content

Alessandro Chiesa: Sampling matchings

by on February 19, 2012

Having a cryptographic bent means I have more reductions in mind than algorithms, BUT:

When I took Costis’ course a year ago, I really liked the Jerrum – Sinclair Markov chain for sampling matchings; it was really the highlight of the course for me.  To me the surprising part was the ability to sample quite structured and different objects (namely, different matchings of a graph) with only very local operations in a way that mixes fast.  Also the exact design and analysis of the Markov chain are clever. Especially the analysis, which uses the technique of “flow encodings” that lets you reason about the mixing time of a Markov chain by studying certain very specific flows on the state graph.

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: