Showing cs.DSShow all
2 papers · 1 filter
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.DS2023
On the hardness of finding balanced independent sets in random bipartite graphs
Will Perkins, Yuzhou Wang
We consider the algorithmic problem of finding large \textit{balanced} independent sets in sparse random bipartite graphs, and more generally the problem of finding independent set…