skip to main content


Search for: All records

Creators/Authors contains: "Perkins, Will"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Kumar, Amit ; Ron-Zewi, Noga (Ed.)
    We study the worst-case mixing time of the global Kawasaki dynamics for the fixed-magnetization Ising model on the class of graphs of maximum degree Δ. Proving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that below the tree uniqueness threshold, the Kawasaki dynamics mix rapidly for all magnetizations. Disproving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that the regime of fast mixing does not extend throughout the regime of tractability for this model: there is a range of parameters for which there exist efficient sampling algorithms for the fixed-magnetization Ising model on max-degree Δ graphs, but the Kawasaki dynamics can take exponential time to mix. Our techniques involve showing spectral independence in the fixed-magnetization Ising model and proving a sharp threshold for the existence of multiple metastable states in the Ising model with external field on random regular graphs. 
    more » « less
    Free, publicly-accessible full text available September 1, 2025
  2. 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
    Free, publicly-accessible full text available January 31, 2025
  3. Abstract

    We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree$\Delta$have a zero-free disc almost as large as the optimal disc for graphs of maximum degree$\Delta$established by Shearer (of radius$\sim 1/(e \Delta )$). Up to logarithmic factors in$\Delta$this is optimal, even for hypergraphs with all edge sizes strictly greater than$2$. We conjecture that for$k\ge 3$,$k$-uniformlinearhypergraphs have a much larger zero-free disc of radius$\Omega (\Delta ^{- \frac{1}{k-1}} )$. We establish this in the case of linear hypertrees.

     
    more » « less
    Free, publicly-accessible full text available January 1, 2025
  4. Abstract

    We prove, under an assumption on the critical points of a real‐valued function, that the symmetric Ising perceptron exhibits the ‘frozen 1‐RSB’ structure conjectured by Krauth and Mézard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1‐RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.

     
    more » « less
  5. Megow, Nicole ; Smith, Adam (Ed.)
    We provide a perfect sampling algorithm for the hard-sphere model on subsets of R^d with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials. 
    more » « less