Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…
cs.DS2025
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 C…