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…