Approximating the Matching Polynomial
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Gives a deterministic algorithmic boundary: positive real weights admit the classical Markov-chain FPRAS, bounded-degree graphs admit a deterministic correlation decay scheme via the self-avoiding-walk tree, and graphs with bounded connective constant also admit a correlation-decay algorithm after reparametrizing gamma by a complex q (Re(q)>0) and proving contraction in a semicircular region with a tailored potential metric. Shows matching hardness: for bounded degree all gamma ≤ −1/(4(Δ−1)) are #P-hard to approximate (and for connective-constant families a dense set of negative reals is hard), achieved by gadget constructions that mimic edge activities with exponentially small error.
AI-written summary · about
chapters (11)
- 0:00Start
- 6:01It suffices to estimate marginal probabilities
- 6:24Correlation Decay 1: It suffices to estimate marginal
- 10:23Computing Marginal Probs on a Tree: Recurrence
- 12:45If "correlation decays", truncate the tree!
- 14:32Method of Barvinok (2015)
- 21:41Connective Constant (Sinclair, Srivastava, Stefanković and Yin 2017)
- 28:43Connective Constant (Sinclair, Srivastava, Štefankovič and Yin 2017)
- 36:17Use a potential function to measure distance
- 36:53Correlation Decay 101
- 38:10Correlation Decay 6