Will Perkins 0001

SODA Conference 2024 Conference Paper

On the hardness of finding balanced independent sets in random bipartite graphs

• Will Perkins 0001
• Yuzhou Wang

FOCS Conference 2024 Conference Paper

Sampling, Counting, and Large Deviations for Triangle-Free Graphs Near the Critical Density

• Matthew Jenssen
• Will Perkins 0001
• Aditya Potukuchi
• Michael Simkin

We study the following combinatorial counting and sampling problems: can we sample from the Erdős-Rényi random graph $G(n, p)$ conditioned on triangle-freeness? Can we approximate (either algorithmically or with a formula) the probability that $G(n, p)$ is triangle-free? These are prototypical instances of forbidden substructure problems ubiquitous in combinatorics. The algorithmic questions are instances of approximate sampling and counting for a hypergraph hard-core model. Estimating the probability that $G(n, p)$ has no triangles is a fundamental question in probabilistic combinatorics and one that has led to the development of many important tools in the field. Through the work of several authors, the asymnpotics of the logarithm of this probability are known if $p=o(n^{-1/2})$ or if $p=\omega(n^{-1/2})$. The regime $p=\Theta(n^{-1/2})$ is more mysterious, as this range witnesses a dramatic change in the the typical structural properties of $G(n, p)$ conditioned on triangle-freeness. As we show, this change in structure has a profound impact on the performance of sampling algorithms. We give two different efficient sampling algorithms for this problem (and complementary approximate counting algorithms), one that is efficient when $p < c/\sqrt{n}$ and one that is efficient when $p > C/\sqrt{n}$ for constants $c, C > 0$. The latter algorithm involves a new approach for dealing with large defects in the setting of sampling from low-temperature spin models. Our algorithmic results can be used to give an asymptotic formula for the logarithm of the probability $G(n, p)$ is triangle-free when $p < c/\sqrt{n}$. This algorithmic approach to large deviation problems in random graphs is very different than the known approaches in the suBCRitical regime $p=o(n^{-1/2})$ (based on the Poisson paradigm) and in the supercritical regime $p=\omega(n^{-1/2})$ (based on regularity lemmas or hypergraph containers); in fact, to the best of our knowledge, no asymptotic formula for the log probability in the regime $p=\Theta(n^{-1/2})$ was even conjectured previously.

FOCS Conference 2022 Conference Paper

Algorithms and Barriers in the Symmetric Binary Perceptron Model

• David Gamarnik
• Eren C. Kizildag
• Will Perkins 0001
• Changji Xu

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be viewed as a random constraint satisfaction problem with a high degree of connectivity. The model and its symmetric variant, the symmetric binary perceptron (SBP), have been studied widely in statistical physics, mathematics, and machine learning. The 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 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 [1], [2]. This suggests that finding a solution to the SBP may be computationally intractable. At the same time, however, the SBP does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in [3]: 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 [4]. 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 statistical-to-computational gap exhibited by this problem. We show that at high enough densities the 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\rightarrow\infty$. We then prove that the m-OGP rules out the class of stable algorithms for the SBP above this threshold. We conjecture that the $m\rightarrow\infty$ limit of the m-OGP threshold marks the algorithmic threshold for the problem. Furthermore, we investigate the stability of known efficient algorithms for perceptron models and show that the Kim-Roche algorithm [5], devised for the asymmetric binary perceptron, is stable in the sense we consider.

STOC Conference 2022 Conference Paper

Approximate counting and sampling via local central limit theorems

• Vishesh Jain
• Will Perkins 0001
• Ashwin Sah
• Mehtaab Sawhney

We give an FPTAS for computing the number of matchings of size k in a graph G of maximum degree Δ on n vertices, for all k ≤ (1−δ) m * ( G ), where δ>0 is fixed and m * ( G ) is the matching number of G , and an FPTAS for the number of independent sets of size k ≤ (1−δ) α c (Δ) n , where α c (Δ) is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size k ≤ (1−δ) m * ( G ) and independent sets of size k ≤ (1−δ)α c (Δ) n .

SODA Conference 2022 Conference Paper

Approximately counting independent sets in bipartite graphs via graph containers

• Matthew Jenssen
• Aditya Potukuchi
• Will Perkins 0001

By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. The first algorithm applies to d -regular, bipartite graphs satisfying a weak expansion condition: when d is constant, and the graph is a Ω(log 2 d/d )-bipartite expander, we obtain an FPTAS for the number of independent sets. Previously such a result for d > 5 was known only for graphs satisfying the much stronger expansion conditions of random graphs. The second algorithm applies to all d -regular, bipartite graphs, runs in time exp, and outputs a (1 + o (1))-approximation to the number of independent sets.

STOC Conference 2022 Conference Paper

Computational thresholds for the fixed-magnetization Ising model

• Charlie Carlson
• Ewan Davies
• Alexandra Kolla
• Will Perkins 0001

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 ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of +1 and −1 spins). In particular, letting β c (Δ) denote the critical inverse temperature of the zero-field Ising model on the infinite Δ-regular tree, and η Δ,β,1 + denote the mean magnetization of the zero-field + measure on the infinite Δ-regular tree at inverse temperature β, we prove, for the class of graphs of maximum degree Δ: (i) for β β c (Δ), there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for magnetizations η such that |η| >η Δ,β,1 + . (iii) For β > β c (Δ), there is no FPRAS for the fixed-magnetization Ising model for magnetizations η such that |η| <η Δ,β,1 + unless NP=RP.

STOC Conference 2021 Conference Paper

Frozen 1-RSB structure of the symmetric Ising perceptron

• Will Perkins 0001
• Changji Xu

We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the `frozen 1-RSB' 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.

SODA Conference 2020 Conference Paper

Counting independent sets in unbalanced bipartite graphs

• Sarah Cannon
• Will Perkins 0001

STOC Conference 2020 Conference Paper

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures

• Christian Borgs
• Jennifer T. Chayes
• Tyler Helmuth
• Will Perkins 0001
• Prasad Tetali

For d ≥ 2 and all q ≥ q 0 ( d ) we give an efficient algorithm to approximately sample from the q -state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ ) d for any inverse temperature β≥ 0. This 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.

STOC Conference 2019 Conference Paper

Algorithmic Pirogov-Sinai theory

• Tyler Helmuth
• Will Perkins 0001
• Guus Regts

We develop an efficient algorithmic approach for approximate counting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice ℤ d and on the torus (ℤ/ n ℤ) d . Our approach is based on combining contour representations from Pirogov–Sinai theory with Barvinok’s approach to approximate counting using truncated Taylor series. Some consequences of our main results include an FPTAS for approximating the partition function of the hard-core model at sufficiently high fugacity on subsets of ℤ d with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus (ℤ/ n ℤ) d at sufficiently low temperature.

SODA Conference 2019 Conference Paper

Algorithms for #BIS-hard problems on expander graphs

• Matthew Jenssen
• Peter Keevash
• Will Perkins 0001

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.

STOC Conference 2017 Conference Paper

Information-theoretic thresholds from the cavity method

• Amin Coja-Oghlan
• Florent Krzakala
• Will Perkins 0001
• Lenka Zdeborová

STOC Conference 2015 Conference Paper

On the Complexity of Random Satisfiability Problems with Planted Solutions

• Vitaly Feldman
• Will Perkins 0001
• Santosh S. Vempala

The problem of identifying a planted assignment given a random k-SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with O(n log n) clauses, there are distributions over clauses for which the best known efficient algorithms require n k/2 clauses. We propose and study a unified model for planted k-SAT, which captures well-known special cases. An instance is described by a planted assignment σ and a distribution on clauses with k literals. We define its distribution complexity as the largest r for which the distribution is not r-wise independent (1 ≤ r ≤ k for any distribution with a planted assignment).

FOCS Conference 2010 Conference Paper

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs

• Irit Dinur
• Subhash Khot
• Will Perkins 0001
• Muli Safra

For every ∈ > 0, and integer q ≥ 3, we show that given an N-vertex graph that has an induced q-colorable subgraph of size (1 - ∈)N, it is NP-hard to find an independent set of size N/q 2.