Nike Sun

SODA Conference 2023 Conference Paper

Sharp threshold sequence and universality for Ising perceptron models

• Shuta Nakajima
• Nike Sun

We study a family of Ising perceptron models with {0, 1}-valued activation functions. This includes the classical half-space models, as well as some of the symmetric models considered in recent works. For each of these models we show that the free energy is self-averaging, there is a sharp threshold sequence, and the free energy is universal with respect to the disorder. A prior work of C. Xu (2019) used very different methods to show a sharp threshold sequence in the half-space Ising perceptron with Bernoulli disorder. Recent works of Perkins-Xu (2021) and Abbe-Li-Sly (2021) determined the sharp threshold and limiting free energy in a symmetric perceptron model. The results of this paper apply in more general settings, and are based on new “add one constraint” estimates extending Talagrand's estimates for the half-space model (1999, 2011). * The full version of the paper can be accessed at https: //arxiv. org/abs/2204. 03469.

STOC Conference 2021 Conference Paper

Statistical physics of random CSPs (tutorial)

• Nike Sun

FOCS Conference 2019 Conference Paper

Breaking of 1RSB in Random Regular MAX-NAE-SAT

• Zsolt Bartha
• Nike Sun
• Yumeng Zhang

For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. In the unsatisfiable regime, it is natural to consider the problem of max-satisfiability: violating the least number of constraints. This is a combinatorial optimization problem on the random energy landscape defined by the problem instance. In the bounded density regime, a very precise estimate of the max-sat value was obtained by Achlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate the nature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) shows that for very large but bounded density, the max-sat value approaches the mean-field (complete graph) limit: this is conjectured to have an "FRSB" structure where near-optimal configurations form clusters within clusters, in an ultrametric hierarchy of infinite depth inside the discrete cube. A stronger form of FRSB was shown in several recent works to have algorithmic implications (again, in complete graphs). Consequently we find it of interest to understand how the model transitions from 1RSB near the satisfiability threshold, to (conjecturally) FRSB at large density. In this paper we show that in the random regular NAE-SAT model, the 1RSB description breaks down by a certain threshold density that we estimate rather precisely. This is proved by an explicit perturbation in the 2RSB parameter space. The choice of perturbation is inspired by the "bug proliferation" mechanism proposed by physicists (Montanari and Ricci-Tersenghi, 2003; Krzakala, Pagnani, and Weigt, 2004), corresponding roughly to a percolation-like threshold for a subgraph of dependent variables.

STOC Conference 2019 Conference Paper

Capacity lower bound for the Ising perceptron

• Jian Ding
• Nike Sun

We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube {−1,+1} N intersected by M random half-spaces. The perceptron’s capacity is the largest integer M N for which the intersection is nonempty. It is conjectured by Krauth and Mézard (1989) that the (random) ratio M N / N converges in probability to an explicit constant α ⋆ ≐ 0.83. Kim and Roche (1998) proved the existence of a positive constant γ such that γ ≤ M N / N ≤ 1−γ with high probability; see also Talagrand (1999). In this paper we show that the Krauth–Mézard conjecture α ⋆ is a lower bound with positive probability, under the condition that an explicit univariate function S (λ) is maximized at λ=0. Our proof is an application of the second moment method to a certain slice of perceptron configurations, as selected by the so-called TAP (Thouless, Anderson, and Palmer, 1977) or AMP (approximate message passing) iteration, whose scaling limit has been characterized by Bayati and Montanari (2011) and Bolthausen (2012). For verifying the condition on S (λ) we outline one approach, which is implemented in the current version using (nonrigorous) numerical integration packages. In a future version of this paper we intend to complete the verification by implementing a rigorous numerical method.

FOCS Conference 2016 Conference Paper

The Number of Solutions for Random Regular NAE-SAT

• Allan Sly
• Nike Sun
• Yumeng Zhang

Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems (CSPs). In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions from the statistical physics literature. Here we revisit one of these models, random regular NAE-SAT: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance. We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction. The proof develops new techniques for analyzing a certain "survey propagation model" associated to this problem. We believe that these methods may be applicable in a wide class of related problems.

STOC Conference 2015 Conference Paper

Proof of the Satisfiability Conjecture for Large k

• Jian Ding
• Allan Sly
• Nike Sun

We establish the satisfiability threshold for random k-SAT for all k ≥ k 0 . That is, there exists a limiting density α s (k) such that a random k-SAT formula of clause density α is with high probability satisfiable for α α s . The satisfiability threshold α s is given explicitly by the one-step replica symmetry breaking (1SRB) prediction from statistical physics. We believe that our methods may apply to a range of random constraint satisfaction problems in the 1RSB class.

STOC Conference 2014 Conference Paper

Satisfiability threshold for random regular NAE-SAT

• Jian Ding
• Allan Sly
• Nike Sun

We consider the random regular k -nae-sat problem with n variables each appearing in exactly d clauses. For all k exceeding an absolute constant k 0 , we establish explicitly the satisfiability threshold d * ∈ d * ( k ). We prove that for d d * the problem is unsatisfiable with high probability. If the threshold d * lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakał a et al. (2007). Our proof verifies the onestep replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

FOCS Conference 2012 Conference Paper

The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs

• Allan Sly
• Nike Sun

The class of two-spin systems contains several important models, including random independent sets and the Ising model of statistical physics. We show that for both the hard-core (independent set) model and the anti-ferromagnetic Ising model with arbitrary external field, it is NP-hard to approximate the partition function or approximately sample from the model on regular graphs when the model has non-uniqueness on the corresponding regular tree. Together with results of Jerrum -- Sinclair, Weitz, and Sinclair -- Srivastava -- Thurley giving FPRAS's for all other two-spin systems except at the uniqueness threshold, this gives an almost complete classification of the computational complexity of two-spin systems on bounded-degree graphs. Our proof establishes that the normalized log-partition function of any two-spin system on bipartite locally tree-like graphs converges to a limiting ``free energy density'' which coincides with the (non-rigorous) Be the prediction of statistical physics. We use this result to characterize the local structure of two-spin systems on locally tree-like bipartite expander graphs, which then become the basic gadgets in a randomized reduction to approximate MAX-CUT. Our approach is novel in that it makes no use of the second moment method employed in previous works on these questions.