8 papers
Local large deviations for triangles in sparse random graphs
Jade Lintott, Will Perkins, Corrine Yap
We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph . Here we aim for first-order asymptotic…
Structural Corrections to the Bethe Approximation of the Permanent
Ijay Narang, Will Perkins
We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight ana…
The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities
Ijay Narang, Will Perkins
We study approximate counting and sampling algorithms for the hard-core model on -regular bipartite graphs under a spectral expansion condition. Let be the biadjacency mat…
Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs
Ijay Narang, Will Perkins, Yuzhou Wang +1
Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposin…
Sampling Colorings with Fixed Color Class Sizes
Aiya Kuchukova, Will Perkins, Xavier Povill
In 1970 Hajnal and Szemerédi proved a conjecture of Erdös that for a graph with maximum degree , there exists an equitable coloring; that is a coloring where color class s…
Fixed-magnetization Ising on random graphs up to reconstruction
Reza Gheissari, Will Perkins, Corrine Yap
We study the fixed-magnetization ferromagnetic Ising model on random -regular graphs for and inverse temperature below the tree reconstruction threshold. Our main resul…
Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
Neng Huang, Will Perkins, Aaron Potechin
We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree for large constant , proving that when the normalized invers…
Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs
Aiya Kuchukova, Marcus Pappik, Will Perkins +1
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 Ca…