Approximate Counting, Markov Chains and Phase Transitions

# click the upper-left icon to select videos from the playlist

source: Simons Institute     2016年2月29日
Approximate Counting, Markov Chains and Phase Transitions
Feb. 22 – Feb. 26, 2016
Markov chains play an important role in a variety of fields, but the analysis of their convergence properties remains a challenging problem. Our emphasis is on the analysis of "large" Markov chains, i.e., finite-state chains where the number of states is exponentially large as a function of the description size of an individual state. Such chains are especially important in the study of statistical physics models and the design of approximate counting algorithms. This workshop will bring together researchers in the analysis of large Markov chains from many areas of application, to review progress and to identify challenges for future research.
Recently there has been considerable success in designing approximate counting algorithms without the use of Markov chains, relying instead on so-called "spatial mixing" properties. Remarkably, matching hardness results have been established in the special case of antiferromagnetic 2-spin systems. This beautiful collection of results ties together the complexity of approximate counting on a general class of graphs with an associated phase transition for the infinite regular tree. By highlighting recent results in the study of approximate counting problems, the workshop will explore analogous connections for other models and for related problems.
For more information, please visit https://simons.berkeley.edu/workshops/counting2016-1.
These presentations were supported in part by an award from the Simons Foundation.

The Complexity of Approximately Counting in 2-spin Systems on k-uniform Bounded-degree Hypergraphs 48:29 Leslie Ann Goldberg, University of Oxford https://simons.berkeley.edu/talks/les...
Dynamics for the Random-Cluster Model 45:20
Local Algorithms for Two Problems on Locally Tree-Like Graphs 44:53
Effect of Initial Conditions on Mixing for Spin Systems 51:24
Cutoff on all Ramanujan Graphs 48:48
Counting Independent Sets in Hypergraphs when Strong Spatial Mixing Fails 46:26
Swendsen-Wang Algorithm on the Mean-Field Potts Model 45:49
Random Walk on Random Directed Graphs 41:48
Random Lattice Triangulations 47:39
Glauber Dynamics of Lattice Triangulations on Thin Rectangles 43:08
SAT Counting and Sampling -- From Theory to Practice 49:01
FPTAS for #BIS with Degree Bounds on One Side 46:59
Curvature, Mixing, and Entropic Interpolation 53:33
Rates of Convergence for 'Features' of a Markov Chain 51:34
Local Graph Coloring 46:02
The Computational Complexity of Estimating Convergence Time 43:09
Local Algorithms for Community Detection 39:00
Learning a Tree-Structured Ising Model in Order to Make Predictions 33:00
Generating Random Permutations Using Switching Networks 35:47
Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics 49:48
An Occupancy Approach to the Hard-Core Model 33:49
Equitable Rectangular Dissections of a Square 37:48