92 citations · 395 across the 40 of their papers we have counts for
53 papers
Satisfiability and freezing in random integer programs
Dylan J. Altschuler, Ruben Ascoli, Will Perkins
We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the locatio…
A simple proof of rapid mixing on random regular graphs beyond uniqueness
Andreas Göbel, Matthew Jenssen, Marcus Michelen +3
A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness thresh…
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…
Percolation on hypergraphs and the hard-core model
Tyler Helmuth, Will Perkins, Michail Sarantis
We prove tight bounds on the site percolation threshold for -uniform hypergraphs of maximum degree and for -uniform hypergraphs of maximum degree in which any pair of…
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…
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
David Gamarnik, Eren C. Kızıldağ, Will Perkins +1
For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This…