License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.21
URN: urn:nbn:de:0030-drops-163622
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16362/
Bezáková, Ivona ;
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Štefankovič, Daniel
Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs
Abstract
Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations.
Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L^p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of L^p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L^p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs.
As a main application of our techniques, we consider the random graph G(n,d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime.
BibTeX - Entry
@InProceedings{bezakova_et_al:LIPIcs.ICALP.2022.21,
author = {Bez\'{a}kov\'{a}, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and \v{S}tefankovi\v{c}, Daniel},
title = {{Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {21:1--21:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16362},
URN = {urn:nbn:de:0030-drops-163622},
doi = {10.4230/LIPIcs.ICALP.2022.21},
annote = {Keywords: Hard-core model, Random graphs, Markov chains}
}
|
Keywords: |
|
Hard-core model, Random graphs, Markov chains |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
