UCSB CS Theory Colloquium Series

Fall 2022

Friday, October 28, Noon Henley Hall 1010

Speaker: Daniel Frishberg (UC Irvine)

Title: Flow-based projection-restriction methods for rapid mixing of geometric and combinatorial Markov chains

Abstract: Projection-restriction, pioneered by Jerrum, Son, Tetali, and Vigoda in a 2004 paper, is an established divide-and-conquer framework for rapid mixing results in certain Markov chains. One partitions the state space of a chain into a collection of smaller restriction chains; if one finds a good lower bound on the spectral gap of the projection chain, this yields rapid mixing for the original chain.

Bounding the spectral gap of the projection chain is an art and a science. One of the simpler methods is to use a multicommodity flow, a purely combinatorial proof technique. Despite their simplicity, multicommodity flows have an Achilles heel: they often fail to give a tight bound for the spectral gap. Nonetheless, we discuss recent bounds by Eppstein and Frishberg for well-studied chains---one of which had resisted progress for 25 years---that show the continued utility of this proof technique.

Bio: Daniel Frishberg is a Ph.D. candidate in Computer Science at the University of California, Irvine. His current research focus is Markov chain mixing times, with recent work on various combinatorial chains in bounded-treewidth graphs, as well as the flip walk on convex point set triangulations. Prior to graduate school, he worked in software development for nonprofits and for the National Institutes of Health. He has two cats, Marvin and Tammi.