92 citations · 395 across the 40 of their papers we have counts for
12 papers · 1 filter
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…
Perfect Sampling for Hard Spheres from Strong Spatial Mixing
Konrad Anand, Andreas Göbel, Marcus Pappik +1
We provide a perfect sampling algorithm for the hard-sphere model on subsets of with expected running time linear in the volume under the assumption of strong spatia…
Fast and perfect sampling of subgraphs and polymer systems
Antonio Blanca, Sarah Cannon, Will Perkins
We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolati…
Computational thresholds for the fixed-magnetization Ising model
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate co…
Approximately counting independent sets in bipartite graphs via graph containers
Matthew Jenssen, Will Perkins, Aditya Potukuchi
By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. Our first…
Approximation algorithms for the random-field Ising model
Tyler Helmuth, Holden Lee, Will Perkins +2
Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and i…
Approximate counting and sampling via local central limit theorems
Vishesh Jain, Will Perkins, Ashwin Sah +1
We give an FPTAS for computing the number of matchings of size in a graph of maximum degree on vertices, for all , where is fixed and $m^*(…
Approximately counting independent sets of a given size in bounded-degree graphs
Ewan Davies, Will Perkins
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density…
Counting independent sets in unbalanced bipartite graphs
Sarah Cannon, Will Perkins
We give an FPTAS for approximating the partition function of the hard-core model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the si…
Fast algorithms at low temperatures via Markov chains
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain…
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…
On the Resilience of Bipartite Networks
Shelby Heinecke, Will Perkins, Lev Reyzin
Motivated by problems modeling the spread of infections in networks, in this paper we explore which bipartite graphs are most resilient to widespread infections under various param…