Conference item
Fast mixing via polymers for random graphs with unbounded degree
- Abstract:
-
The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this ass...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, 648.7KB)
-
- Publisher copy:
- 10.4230/LIPIcs.APPROX/RANDOM.2021.36
Authors
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Host title:
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
- Series:
- Leibniz International Proceedings in Informatics
- Volume:
- 207
- Pages:
- 36:1--36:13
- Publication date:
- 2021-09-15
- Acceptance date:
- 2021-06-23
- Event title:
- 25th International Conference on Randomization and Computation (RANDOM)
- Event location:
- Virtual Event
- Event website:
- https://randomconference.com/random-2021-home/
- Event start date:
- 2021-08-16
- Event end date:
- 2021-08-18
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 978-3-95977-207-5
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
1183220
- Local pid:
- pubs:1183220
- Deposit date:
- 2021-06-24
Terms of use
- Copyright holder:
- Galanis et al.
- Copyright date:
- 2021
- Rights statement:
- © Andreas Galanis, Leslie Ann Goldberg, and James Stewart; licensed under Creative Commons License CC-BY 4.0
- Notes:
- This paper was presented at the 25th International Conference on Randomization and Computation (RANDOM)
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record