Will Perkins
YOU?
Author Swipe
View article: Fast and Slow Mixing of the Kawasaki Dynamics on Bounded‐Degree Graphs
Fast and Slow Mixing of the Kawasaki Dynamics on Bounded‐Degree Graphs Open
We study the worst‐case mixing time of the global Kawasaki dynamics for the fixed‐magnetization Ising model on the class of graphs of maximum degree . Proving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that below the tree…
View article: On the evolution of structure in triangle-free graphs
On the evolution of structure in triangle-free graphs Open
We study the typical structure and the number of triangle-free graphs with n vertices and m edges where m is large enough so that a typical triangle-free graph has a cut containing nearly all of its edges, but may not be bipartite. Erdős, …
View article: On the chromatic number of random triangle-free graphs
On the chromatic number of random triangle-free graphs Open
We study the chromatic number of typical triangle-free graphs with $Θ\left( n^{3/2} (\log n)^{1/2} \right)$ edges and establish the width of the scaling window for the transitions from $χ= 3$ to $χ= 4$ and from $χ= 4$ to $χ= 5$. The transi…
View article: The typical structure of dense claw-free graphs
The typical structure of dense claw-free graphs Open
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 logarithm of the number of claw-free graphs of edge density $γ\in …
View article: Is there a superlative rabbit in the ordinal hat? A study of ordinals vs. degree modifiers in nested definites
Is there a superlative rabbit in the ordinal hat? A study of ordinals vs. degree modifiers in nested definites Open
This study probes how the semantics of ordinals relates to the semantics of comparatives and superlatives. We examine this question with the help of a picture task in which participants are asked to locate objects described by nested descr…
View article: Lower tails for triangles inside the critical window
Lower tails for triangles inside the critical window Open
We study the probability that the random graph $G(n,p)$ is triangle-free. When $p =o(n^{-1/2})$ or $p = ω(n^{-1/2})$ the asymptotics of the logarithm of this probability are known via Janson's inequality in the former case and via regulari…
View article: Pirogov--Sinai Theory Beyond Lattices
Pirogov--Sinai Theory Beyond Lattices Open
Pirogov--Sinai theory is a well-developed method for understanding the low-temperature phase diagram of statistical mechanics models on lattices. Motivated by physical and algorithmic questions beyond the setting of lattices, we develop a …
View article: Sampling and counting triangle-free graphs near the critical density
Sampling and counting triangle-free graphs near the critical density Open
We study the following combinatorial counting and sampling problems: can we efficiently sample from the Erdős-Rényi random graph $G(n,p)$ conditioned on triangle-freeness? Can we efficiently approximate the probability that $G(n,p)$ is tri…
View article: Searching for (sharp) thresholds in random structures: Where are we now?
Searching for (sharp) thresholds in random structures: Where are we now? Open
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 Park and Pham and the fairly recent proof of the satisfiability…
View article: Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
Hardness of sampling for the anti-ferromagnetic Ising model on random graphs Open
We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree $d$ for large constant $d$, proving that when the normalized inverse temperature satisfies $β>1$ (asymptotically corresponding…
View article: Searching for (sharp) thresholds in random structures: where are we now?
Searching for (sharp) thresholds in random structures: where are we now? Open
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 Park and Pham and the fairly recent proof of the satisfiabilit…
View article: On the evolution of structure in triangle-free graphs
On the evolution of structure in triangle-free graphs Open
We study the typical structure and the number of triangle-free graphs with $n$ vertices and $m$ edges where $m$ is large enough so that a typical triangle-free graph has a cut containing nearly all of its edges, but may not be bipartite. E…
View article: On the zeroes of hypergraph independence polynomials
On the zeroes of hypergraph independence polynomials Open
We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free re…
View article: Approximation Algorithms for the Random Field Ising Model
Approximation Algorithms for the Random Field Ising Model Open
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 it is widely believed that no polynomial-time approximation …
View article: On the hardness of finding balanced independent sets in random bipartite graphs
On the hardness of finding balanced independent sets in random bipartite graphs Open
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 sets with specified proportions of vertices on each side of th…
View article: Percolation on hypergraphs and the hard-core model
Percolation on hypergraphs and the hard-core model Open
We prove tight bounds on the site percolation threshold for $k$-uniform hypergraphs of maximum degree $Δ$ and for $k$-uniform hypergraphs of maximum degree $Δ$ in which any pair of edges overlaps in at most $r$ vertices. The hypergraphs th…
View article: Perfect Sampling for Hard Spheres from Strong Spatial Mixing
Perfect Sampling for Hard Spheres from Strong Spatial Mixing Open
We provide a perfect sampling algorithm for the hard-sphere model on subsets of $\mathbb{R}^d$ with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate samplin…
View article: Maximum entropy and integer partitions
Maximum entropy and integer partitions Open
We derive asymptotic formulas for the number of integer partitions with given sums of \(j\)th powers of the parts for \(j\) belonging to a finite, non-empty set \(J \subset \mathbb N\). The method we use is based on the `principle of maxim…
View article: Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization Open
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 is often accomplished through the lens of the multi Overlap…
View article: Efficient sampling and counting algorithms for the Potts model on <i>ℤ</i><sup><i>d</i></sup> at all temperatures
Efficient sampling and counting algorithms for the Potts model on <i>ℤ</i><sup><i>d</i></sup> at all temperatures Open
For and all we give an efficient algorithm to approximately sample from the ‐state ferromagnetic Potts and random cluster models on finite tori for any inverse temperature . This shows that the physical phase transition of the Potts model …
View article: On the zeroes of hypergraph independence polynomials
On the zeroes of hypergraph independence polynomials Open
We study the locations of complex zeroes of independence polynomials of bounded degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free re…
View article: Correlation decay for hard spheres via Markov chains
Correlation decay for hard spheres via Markov chains Open
No description supplied
View article: Algorithms and Barriers in the Symmetric Binary Perceptron Model
Algorithms and Barriers in the Symmetric Binary Perceptron Model Open
The symmetric binary perceptron ($\texttt{SBP}$) exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far below the threshold for the existence of solutions. Furthermore…
View article: Fast and perfect sampling of subgraphs and polymer systems
Fast and perfect sampling of subgraphs and polymer systems Open
We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and wor…
View article: Independent sets of a given size and structure in the hypercube
Independent sets of a given size and structure in the hypercube Open
We determine the asymptotics of the number of independent sets of size $\lfloor \beta 2^{d-1} \rfloor$ in the discrete hypercube $Q_d = \{0,1\}^d$ for any fixed $\beta \in (0,1)$ as $d \to \infty$ , extending a result of Galvin for $\beta …
View article: Data from: Three simple scenarios for high-dimensional sphere packings
Data from: Three simple scenarios for high-dimensional sphere packings Open
Based on results from the physics and mathematics literature which suggest a series of clearly defined conjectures, we formulate three simple scenarios for the fate of hard sphere crystallization in high dimension: in scenario A, crystalli…
View article: Computational thresholds for the fixed-magnetization Ising model
Computational thresholds for the fixed-magnetization Ising model Open
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 counting: approximating the partition function of the ferroma…
View article: Approximately counting independent sets in bipartite graphs via graph containers
Approximately counting independent sets in bipartite graphs via graph containers Open
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 algorithm applies to $d$-regular, bipartite graphs satisfy…