11 citations · 13 across the 6 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Sampling and counting triangle-free graphs near the critical density
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We study the following combinatorial counting and sampling problems: can we efficiently sample from the Erdős-Rényi random graph conditioned on triangle-freeness? Can we e…
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…
cs.DS2014★ 11 cited
Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
Vitaly Feldman, Will Perkins, Santosh Vempala
We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems, via a common generalizat…