Markov Chain Mixing Times and Applications III
summary
Introduces conductance bounds tied to spectral gap and uses conductance and canonical paths to get explicit mixing-time estimates, then builds canonical paths for matchings to show congestion is O(number of matchings) so the sliding chain mixes in polynomial time (gives an FPRAS for counting matchings); analyzes the swap chain and constructs an exponential-separation gadget that proves it can require exponential time; presents a perfect-matching annealing scheme using weighted sampling and near‑perfect to perfect flow to obtain a randomized approximation for the permanent on bipartite graphs.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:13Outline
- 2:45Conductance
- 6:32Canonical Paths
- 14:44Matchings Revisited
- 15:24A Markov Chain for Matchings
- 21:16Bounding the Congestion Congestion through transition MM
- 23:49Bounding the Congestion: Encoding
- 33:13A Markov Chain for Perfect Matchings
- 42:23Another MC for Perfect Matchings
- 47:09Back to the Sliding Chain: Permanent
related talks
23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
30mStreaming Lower Bounds for Approximating MAX-CUT
01h 09mInformation Theory in Computational Complexity IV
33mWelfare Maximization with Limited Interaction: Information and Communication in Economics
50mRandom Combinatorial Matrices
31mAnswering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations
01h 00mAverage-case Complexity for Polynomials, and All That
27mSmall Value Parallel Repetition for General Games