skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Fast algorithms at low temperatures via Markov chains†
Efficient algorithms for approximate counting and sampling in spin systems typically apply in the so‐called high‐temperature regime, where the interaction between neighboring spins is “weak.” Instead, recent work of Jenssen, Keevash, and Perkins yields polynomial‐time algorithms in the low‐temperature regime on bounded‐degree (bipartite) expander graphs using polymer models and the cluster expansion. In order to speed up these algorithms (so the exponent in the run time does not depend on the degree bound) we present a Markov chain for polymer models and show that it is rapidly mixing under exponential decay of polymer weights. This yields, for example, an‐time sampling algorithm for the low‐temperature ferromagnetic Potts model on bounded‐degree expander graphs. Combining our results for the hard‐core and Potts models with Markov chain comparison tools, we obtain polynomial mixing time for Glauber dynamics restricted to appropriate portions of the state space.  more » « less
Award ID(s):
1847451 1934915
PAR ID:
10196575
Author(s) / Creator(s):
 ;  ;  ;  ;  ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Volume:
58
Issue:
2
ISSN:
1042-9832
Page Range / eLocation ID:
p. 294-321
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022))
    Chakrabarti, Amit; Swamy, Chaitanya (Ed.)
    We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability p ∈ (0,1) and a cluster weight q > 0. We establish that for every q ≥ 1, the random-cluster Glauber dynamics mixes in optimal Θ(nlog n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching γ throughout the full high-temperature uniqueness regime p < p_u(q,γ). The family of random graph models we consider includes the Erdős-Rényi random graph G(n,γ/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erdős-Rényi random graphs for the full tree uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the largest degree) for the Potts Glauber dynamics, in the same settings where our Θ(n log n) bounds for the random-cluster Glauber dynamics apply. This reveals a novel and significant computational advantage of random-cluster based algorithms for sampling from the Potts model at high temperatures. 
    more » « less
  2. ; ; (, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022))
    Chakrabarti, Amit; Swamy, Chaitanya (Ed.)
    We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications. 
    more » « less
  3. ; ; (, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022))
    Chakrabarti, Amit; Swamy, Chaitanya (Ed.)
    We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications. 
    more » « less
  4. ; ; (, ACM Transactions on Algorithms)
    We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (orgraphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications. 
    more » « less
  5. ; (, Random Structures & Algorithms)
    We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information‐theoretic limit of graph sparsity in time polynomial in the number of verticesn. Moreover, we show the number of seeds needed for perfect recovery in polynomial‐time can be as low asin the sparse graph regime (with the average degree smaller than) andin the dense graph regime, for a small positive constant. Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email