2 citations · 3 across the 8 of their papers we have counts for
12 papers
The replica symmetric solution for hypergraph independent sets in the critical regime
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We prove a variational formula for the logarithmic asymptotics of a non-existence probability in a broad class of combinatorial problems such as avoiding cliques in random graphs a…
Non-existence probabilities and lower tails in the critical regime via Belief Propagation
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of…
Optimal detection of planted stars via a random energy model
Ijay Narang, Will Perkins, Timothy L. H. Wee
We study the problem of detecting a planted star in the Erd{ő}s--R{é}nyi random graph , formulated as a hypothesis test. We determine the scaling window for critical detect…
On the chromatic number of random triangle-free graphs
Clayton Mizgerd, Will Perkins, Yuzhou Wang
We study the chromatic number of typical triangle-free graphs with edges and establish the width of the scaling window for the transitions…
The typical structure of dense claw-free graphs
Will Perkins, Sam van der Poel
We analyze the asymptotic number and typical structure of claw-free graphs at constant edge densities. The first of our main results is a formula for the asymptotics of the logarit…
Lower tails for triangles inside the critical window
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We study the probability that the random graph is triangle-free. When or the asymptotics of the logarithm of this probability are known…
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…
Searching for (sharp) thresholds in random structures: where are we now?
Will Perkins
We survey the current state of affairs in the study of thresholds and sharp thresholds in random structures on the occasion of the recent proof of the Kahn--Kalai Conjecture by Par…
On the evolution of structure in triangle-free graphs
Matthew Jenssen, Will Perkins, Aditya Potukuchi
We study the typical structure and the number of triangle-free graphs with vertices and edges where is large enough so that a typical triangle-free graph has a cut cont…
Algorithms for #BIS-hard problems on expander graphs
Matthew Jenssen, Peter Keevash, Will Perkins
We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts m…
Counting independent sets in cubic graphs of given girth
Guillem Perarnau, Will Perkins
We prove a tight upper bound on the independence polynomial (and total number of independent sets) of cubic graphs of girth at least 5. The bound is achieved by unions of the Heawo…
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman, Will Perkins, Santosh Vempala
The problem of identifying a planted assignment given a random -SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes u…