Français
Sampling algorithms and phase transitions
Post-edited
Authors : ...
CIRM (Publisher )
60C05 - Combinatorial probability
60J20 - Applications of Markov chains and discrete-time Markov processes on general state spaces
68R05 - Combinatorics in connection with computer science
Additional resources :
https://www.cirm-math.fr/RepOrga/1940/Slides/Randall-slides.pdf
CIRM (Publisher )
Loading the player...
|
| monotonic surfaces Markov chains integer partitions Boltzmann sampling the 6-vertex model slow mixing |
Abstract :
Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large combinatorial sets. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they abruptly change from being efficient to inefficient as some parameter of the system is modified. Generating functions can offer an alternative approach to sampling and they play a role in showing when certain Markov chains are efficient or not. We will explore the interplay between Markov chains, generating functions, and phase transitions for a variety of combinatorial problems, including graded posets, Boltzmann sampling, and 3-colorings on $Z^{2}$.
Keywords : Markov chain; phase transition; integer partitions; 3-colorings
MSC Codes : Keywords : Markov chain; phase transition; integer partitions; 3-colorings
60C05 - Combinatorial probability
60J20 - Applications of Markov chains and discrete-time Markov processes on general state spaces
68R05 - Combinatorics in connection with computer science
Additional resources :
https://www.cirm-math.fr/RepOrga/1940/Slides/Randall-slides.pdf
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 26/07/2019 Conference Date : 24/06/2019 Subseries : Research talks arXiv category : Computer Science ; Combinatorics ; Mathematical Physics ; Probability Mathematical Area(s) : Computer Science ; Combinatorics ; Probability & Statistics Format : MP4 (.mp4) - HD Video Time : 01:10:29 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2019-06-24_Randall.mp4 
|
Information on the Event
Event Title : AofA: Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms / AofA: méthodes probabilistes, combinatoires et asymptotiques pour l analyse d algorithmesEvent Organizers : Bassino, Frédérique ; Martínez, Conrado ; Salvy, Bruno Dates : 24/06/2019 - 28/06/2019 Event Year : 2019 Event URL : https://conferences.cirm-math.fr/1940.html
Citation Data
DOI : 10.24350/CIRM.V.19540103Cite this video as: (2019). Sampling algorithms and phase transitions. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19540103 URI : http://dx.doi.org/10.24350/CIRM.V.19540103 |
See Also
- [Multi angle] Algorithms in high-dimensional non-convex landscapes / Author of the conference Zdeborova, Lenka.
- [Multi angle] The challenge of linear-time Boltzmann sampling / Author of the conference Sportiello, Andrea.
- [Multi angle] Metastability of the contact process on evolving scale-free networks / Author of the conference Mörters, Peter.
- [Multi angle] Computer algebra for lattice path combinatorics / Author of the conference Bostan, Alin.
Bibliography
- LUBY, Michael, RANDALL, Dana, et SINCLAIR, Alistair. Markov chain algorithms for planar lattice structures. SIAM journal on Computing, 2001, vol. 31, no 1, p. 167-192. - https://doi.org/10.1137/S0097539799360355
- BHAKTA, Prateek, COUSINS, Ben, FAHRBACH, Matthew, et al. Approximately sampling elements with fixed rank in graded posets. In : Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017. p. 1828-1838. - https://doi.org/10.1137/1.9781611974782.119
- FAHRBACH, Matthew et RANDALL, Dana. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ferroelectric and Antiferroelectric Phases. arXiv preprint arXiv:1904.01495, 2019. - https://arxiv.org/abs/1904.01495
