Local Algorithms for Two Problems on Locally Tree-Like Graphs

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=Rgcs-y-fxAw


Duration: 44:53
426 views
2

Andrea Montanari, Stanford University
Approximate Counting, Markov Chains and Phase Transitions
https://simons.berkeley.edu/talks/andrea-montanari-02-22-2016



Other Videos By Simons Institute for the Theory of Computing


2016-03-11Chromatin Dynamics and Gene Regulation During Motor Neuron Programming
2016-02-29Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics
2016-02-29Equitable Rectangular Dissections of a Square
2016-02-29An Occupancy Approach to the Hard-Core Model
2016-02-29Rates of Convergence for 'Features' of a Markov Chain
2016-02-29The Computational Complexity of Estimating Convergence Time
2016-02-29Local Graph Coloring
2016-02-29Local Algorithms for Community Detection
2016-02-29Generating Random Permutations Using Switching Networks
2016-02-29Learning a Tree-Structured Ising Model in Order to Make Predictions
2016-02-29Local Algorithms for Two Problems on Locally Tree-Like Graphs
2016-02-29Counting Independent Sets in Hypergraphs when Strong Spatial Mixing Fails
2016-02-29Swendsen-Wang Algorithm on the Mean-Field Potts Model
2016-02-29Random Walk on Random Directed Graphs
2016-02-29Cutoff on all Ramanujan Graphs
2016-02-29Effect of Initial Conditions on Mixing for Spin Systems
2016-02-29Random Lattice Triangulations
2016-02-29Glauber Dynamics of Lattice Triangulations on Thin Rectangles
2016-02-29FPTAS for #BIS with Degree Bounds on One Side
2016-02-29Curvature, Mixing, and Entropic Interpolation
2016-02-29SAT Counting and Sampling -- From Theory to Practice


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Counting Complexity and Phase Transitions
Andrea Montanari