BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Will Perkins

Will Perkins contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.PRmath.COData Structures and Algorithmsmath-phmath.MPComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2022arXiv

Algorithms and Barriers in the Symmetric Binary Perceptron Model

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, the $\texttt{SBP}$ exhibits a striking structural property: at all positive constraint densities almost all of its solutions are 'totally frozen' singletons separated by large Hamming distance \cite{perkins2021frozen,abbe2021proof}. This suggests that finding a solution to the $\texttt{SBP}$ may be computationally intractable. At the same time, the $\texttt{SBP}$ does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in \cite{baldassi2020clustering}: efficient algorithms succeed in the face of freezing by finding exponentially rare clusters of large size. However, it was discovered recently that such rare large clusters exist at all subcritical densities, even at those well above the limits of known efficient algorithms \cite{abbe2021binary}. Thus the driver of the statistical-to-computational gap exhibited by this model remains a mystery. In this paper, we conduct a different landscape analysis to explain the algorithmic tractability of this problem. We show that at high enough densities the $\texttt{SBP}$ exhibits the multi Overlap Gap Property ($m-$OGP), an intricate geometrical property known to be a rigorous barrier for large classes of algorithms. Our analysis shows that the $m-$OGP threshold (a) is well below the satisfiability threshold; and (b) matches the best known algorithmic threshold up to logarithmic factors as $m\to\infty$. We then prove that the $m-$OGP rules out the class of stable algorithms for the $\texttt{SBP}$ above this threshold. We conjecture that the $m \to \infty$ limit of the $m$-OGP threshold marks the algorithmic threshold for the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient sampling and counting algorithms for the Potts model on $\mathbb Z^d$ at all temperatures

For $d \ge 2$ and all $q\geq q_{0}(d)$ we give an efficient algorithm to approximately sample from the $q$-state ferromagnetic Potts and random cluster models on finite tori $(\mathbb Z / n \mathbb Z )^d$ for any inverse temperature $β\geq 0$. This shows that the physical phase transition of the Potts model presents no algorithmic barrier to efficient sampling, and stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen--Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models at all temperatures. Our algorithms are based on representing the random cluster model as a contour model using Pirogov--Sinai theory, and then computing an accurate approximation of the logarithm of the partition function by inductively truncating the resulting cluster expansion. The main innovation of our approach is an algorithmic treatment of unstable ground states, which is essential for our algorithms to apply to all inverse temperatures $β$. By treating unstable ground states our work gives a general template for converting probabilistic applications of Pirogov-Sinai theory to efficient algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Independent sets in the hypercube revisited

We revisit Sapozhenko's classic proof on the asymptotics of the number of independent sets in the discrete hypercube $\{0,1\}^d$ and Galvin's follow-up work on weighted independent sets. We combine Sapozhenko's graph container methods with the cluster expansion and abstract polymer models, two tools from statistical physics, to obtain considerably sharper asymptotics and detailed probabilistic information about the typical structure of (weighted) independent sets in the hypercube. These results refine those of Korshunov and Sapozhenko and Galvin, and answer several questions of Galvin.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Independent sets of a given size and structure in the hypercube

We determine the asymptotics of the number of independent sets of size $\lfloor β2^{d-1} \rfloor$ in the discrete hypercube $Q_d = \{0,1\}^d$ for any fixed $β\in [0,1]$ as $d \to \infty$, extending a result of Galvin for $β\in [1-1/\sqrt{2},1]$. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $λ>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Strong spatial mixing for repulsive point processes

We prove that a Gibbs point process interacting via a finite-range, repulsive potential $ϕ$ exhibits a strong spatial mixing property for activities $λ< e/Δ_ϕ$, where $Δ_ϕ$ is the potential-weighted connective constant of $ϕ$, defined recently in [MP21]. Using this we derive several analytic and algorithmic consequences when $λ$ satisfies this bound: (1) We prove new identities for the infinite volume pressure and surface pressure of such a process (and in the case of the surface pressure establish its existence). (2) We prove that local block dynamics for sampling from the model on a box of volume $N$ in $\mathbb R^d$ mixes in time $O(N \log N)$, giving efficient randomized algorithms to approximate the partition function and approximately sample from these models. (3) We use the above identities and algorithms to give efficient approximation algorithms for the pressure and surface pressure.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Frozen $1$-RSB structure of the symmetric Ising perceptron

We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the `frozen 1-RSB&#39; structure conjectured by Krauth and Mezard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algorithms for #BIS-hard problems on expander graphs

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 model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) $Δ$-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite $Δ$-regular tree. We also find efficient counting and sampling algorithms for proper $q$-colorings of random $Δ$-regular bipartite graphs when $q$ is sufficiently small as a function of $Δ$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Maximum entropy and integer partitions

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 maximum entropy&#39; of Jaynes. This principle leads to an intuitive variational formula for the asymptotics of the logarithm of the number of constrained partitions as the solution to a convex optimization problem over real-valued functions.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Tight bounds on the coefficients of partition functions via stability

Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hard-core model and monomer-dimer model are the independence and matching polynomials respectively. We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of $q$-colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least $5$.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Extremes of the internal energy of the Potts model on cubic graphs

We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all $q \ge 2$. This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of $q$-colorings of a $3$-regular graph, for any $q \ge 2$, is maximized by a union of $K_{3,3}$&#39;s. This proves the $d=3$ case of a conjecture of Galvin and Tetali.

0 citations0 reviewsNo code linkedOpen access