Approximate Counting, Markov Chains and Phase Transitions
2016-02-22..2016-02-26
Berkeley, United States
[Random Instances and Phase Transitions (Simons Institute, 2016), The Classification Program of Counting Complexity, Computational Phase Transitions (Simons Institute, 2020), Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019), Interactive Complexity 2018, Functional Inequalities in Discrete Spaces with Applications 2013]
| title | author | length |
|---|---|---|
| The Complexity of Approximately Counting in 2-spin Systems on k-uniform Bounded-degree Hypergraphs | Leslie Ann Goldberg | 48m |
Classifies complexity for symmetric Boolean k-ary constraints on k‑uniform bounded‑degree hypergraphs: any nontrivial function has a degree Delta beyond which… | ||
| Dynamics for the Random-Cluster Model | Antonio Blanca | 45m |
Proves a comparison inequality showing Chayes–Machta global updates and single-edge heat‑bath mix within polynomial factors; analyzes the mean‑field complete… | ||
| Local Algorithms for Two Problems on Locally Tree-Like Graphs | Andrea Montanari | 45m |
Andrea Montanari, Stanford University
Approximate Counting, Markov Chains and Phase Transitions
https://simons.berkeley.edu/talks/andrea-montanari-02-22-2016 | ||
| Effect of Initial Conditions on Mixing for Spin Systems | Eyal Lubetzky | 51m |
Eyal Lubetzky, New York University
Approximate Counting, Markov Chains and Phase Transitions
https://simons.berkeley.edu/talks/eyal-lubetzky-02-22-2016 | ||
| Cutoff on all Ramanujan Graphs | Yuval Peres | 49m |
Any sequence of non-bipartite d-regular Ramanujan graphs has simple random walk cutoff at time d/(d-2) · log_{d-1} n with only lower-order corrections, and the… | ||
| Counting Independent Sets in Hypergraphs when Strong Spatial Mixing Fails | Andreas Galanis | 46m |
Andreas Galanis, University of Oxford
Approximate Counting, Markov Chains and Phase Transitions
https://simons.berkeley.edu/talks/andreas-galanis-02-23-2016 | ||
| Swendsen-Wang Algorithm on the Mean-Field Potts Model | Daniel Stefankovic | 46m |
Analyzes the Swendsen–Wang chain on the complete-graph Potts model and pins mixing regimes to two explicit thresholds: below the first threshold the chain… | ||
| Random Walk on Random Directed Graphs | Justin Salez | 42m |
Random walks on the directed configuration model with bounded degrees exhibit cutoff at time approximately log N divided by μ where μ is the average log… | ||
| Random Lattice Triangulations | Alexandre Stauffer | 48m |
Defines lattice triangulations on the n×n integer grid, puts the Gibbs weight mu(σ) ∝ λ^{total L1 edge length}, and uses Glauber flips (diagonal flip of a… | ||
| Glauber Dynamics of Lattice Triangulations on Thin Rectangles | Fabio Martinelli | 43m |
Proves concrete mixing bounds for lattice triangulations on rectangles with fixed height m: O(n^2) mixing for λ<1 using path coupling with an exponential… | ||
| SAT Counting and Sampling -- From Theory to Practice | Moshe Vardi | 49m |
Moshe Vardi, Rice University
Approximate Counting, Markov Chains and Phase Transitions
https://simons.berkeley.edu/talks/moshe-vardi-02-23-2016 | ||
| FPTAS for #BIS with Degree Bounds on One Side | Pinyan Lu | 47m |
Pinyan Lu, Shanghai University of Finance and Economics
Approximate Counting, Markov Chains and Phase… | ||
| Curvature, Mixing, and Entropic Interpolation | James Lee | 54m |
Shows that a positive coarse Ricci curvature (one-step contracting coupling with rate κ) implies a quantitative W1-entropy transport inequality (transport cost… | ||
| Rates of Convergence for 'Features' of a Markov Chain | Persi Diaconis | 52m |
Shows that many natural features mix far faster than global distance: simple walk on Z_p mixes a half-circle feature in p squared steps but parity in O(1)… | ||
| Local Graph Coloring | Alexander Holroyd | 46m |
Constructs finitary factor of iid (ffiid) proper colorings on Z^d and proves tight coding-radius rates: for d≥2 three-color ffiid colorings exist with… | ||
| The Computational Complexity of Estimating Convergence Time | Nayantara Bhatnagar | 43m |
Constructs Markov chains whose states are Turing‑machine configurations (edges given by a circuit) and tunes an edge weight W so that yes‑instances mix in poly… | ||
| Local Algorithms for Community Detection | Elchanan Mossel | 39m |
Studies reconstruction on a Poisson D tree and gives exact conditions when noisy boundary labels give the same root-recovery probability as perfect labels… | ||
| Learning a Tree-Structured Ising Model in Order to Make Predictions | Guy Bresler | 33m |
Claim: learning a tree Ising model only to get accurate pairwise posteriors needs far fewer samples than learning the exact graph. Method: compute empirical… | ||
| Generating Random Permutations Using Switching Networks | Artur Czumaj | 36m |
Almost every fixed switching network of logarithmic depth yields a distribution that is uniform on 99% of elements; proofs use expansion of short layered… | ||
| Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics | Cris Moore | 50m |
Improves the rigorous lower bound for rapid mixing of a global‑move hard disk Glauber chain from 0.125 to 0.154 density by designing an optimized continuous… | ||
| An Occupancy Approach to the Hard-Core Model | Will Perkins | 34m |
Shows that the natural repulsion inequality—expected excluded volume increases when centers are conditioned non-overlapping—actually fails in dimension 24 via… | ||
| Equitable Rectangular Dissections of a Square | Dana Randall | 38m |
Partitioning an n-by-n square into n lattice rectangles only makes sense when n is a power of two, and the edge-flip chain on those dissections is provably… | ||
| nothing matches | ||