WorksMathematics
The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution
Abstract
The satisfiability conjecture was one of the most important open problems in discrete probability. It was resolved recently first by Carenini~\cite{GCarenini}, and shortly after by OpenAI~\cite{k-sat-OpenAI}, among other 370 problems solved by its internal model. The conjecture concerned the satisfiability property of random instances of the k-SAT problem. It posits the existence of a fixed value for the clause-to-variables ratio around which the probability that the formula is satisfiable drops sharply from nearly one to nearly zero as the ratio increases. While the case of large constant was resolved a decade ago by Ding, Sly and Sun~\cite{ding2015proof,ding2022proof} using the heavy machinery of the second moment method, the case of general eluded proof until ~\cite{GCarenini} and~\cite{k-sat-OpenAI}. In this short note we provide a ''human-friendly'' and detailed exposition of the OpenAI's resolution of the conjecture.
Introduction
The satisfiability conjecture was one of the most important open problems in discrete probability and theoretical computer science areas in the last several decades. It concerns random instances of a particular class of constraint satisfaction problems known as k-SAT problem. The k-SAT problem concerns the satisfiability property of a k-SAT Boolean formula with clauses of size and variables, see the next section for the formal description of the model and the statement of the conjecture. The conjecture posits that for each there exists a fixed value with the following property: the probability that the formula is satisfiable (not-satisfiable) is asymptotically one (asymptotically zero) when is uniformly smaller (uniformly larger) than and diverges to infinity. Namely, the probability of satisfiability exhibits a sharp phase transition around some constant value . The conjecture was positively resolved recently, first by Carenini [5], and shortly after by OpenAI [17]. The paper produced by OpenAI was one among 721 papers produced by the organization devoted to resolving some 372 open problems. The present paper is devoted to producing a reader-friendly exposition of the OpenAI paper. While the manuscript [17] is fairly short and readable on a purely technical level, in a fashion typical for the works produced by AI only, it is not optimized for the readership, contains unnecessary redundancies, applies an uncommon jargon and obscures key ideas. The present manuscript is devoted to fix this. Part of my motivation to write this manuscript was to understand and internalize the proof myself.
A brief history of the conjecture
The conjecture was formulated in Chvátal and Reed [7] who also resolved the conjecture positively for the case . In particular, they proved . The progress beyond stalled however for several decades, despite many papers devoted to the subject and dramatic progress, particularly in narrowing the potential values of , assuming its validity, see for example [3, 2, 8]. Furthermore, sharp phase transition property was established for the satisfiability property for all by Friedgut in his landmark paper [13]. This work produced necessary and sufficient conditions for the existence of sharp transition for general random graph and random hypergraph properties, of which satisfiability of a random -SAT formula is a special case. Unfortunately, however, it did not resolve the conjecture itself. The import from Friedgut’s main result was existence of a potentially -dependent sequence such that the probability of satisfiability is asymptotically one (asymptotically zero) when is asymptotically smaller (asymptotically larger) than and . In other words, while the sharpness of the transition was established, the convergence of its location was not, and as such the location could potentially fluctuate as a function of .
A dramatic progress towards resolving the conjecture was initiated in the field of statistical mechanics, specifically the field of spin glasses. Specifically, Guerra and Toninelli [11] invented an important interpolation technique, using which they proved the existence of the ground state energy limit for the so-called Sherrington-Kirkpatrick model. This approach was instrumental for validating the ground state energy value for this model, computed earlier by Parisi [19, 20] using non-rigorous replica symmetry breaking method. Specifically, the interpolation technique was used by Guerra [14] to prove that the value computed by Parisi is a correct upper bound on the limiting ground state energy value. The matching lower bound was established in a breakthrough work of Talagrand [21] and further developed in many follow up papers, see Panchenko [18].
Next, closer to the random -SAT setting, Franz and Leone [12] adapted the interpolation technique to the setting of diluted spin glass models, which includes random -SAT model as a special case. A corollary of their main result is the existence of the limiting value for the largest number of satisfiable clauses normalized by for the random -SAT formula. The largest number of satisfiable clauses is called the ground state energy in the statistical physics parlance. The interpolation technique employed in [11] and [12] implied superadditivity property of the expectation of the ground state energy: the expected ground state energy on the -variable model is at least the sum of the expected ground state energies of the and -variable models when . The existence of the limit was then a simple application of Fekete’s Lemma. Both papers relied on introducing positive temperature parameter in the respective models and then taking the temperature value to zero in the limit.
The next development came from Bayati, Gamarnik and Tetali [4] who adapted Franz and Leone’s interpolation technique directly to the zero-temperature optimization problems. The results in this paper had implications for the satisfiability property of random -SAT formulas per se. Specifically, log-superadditivity of the satisfiability property was established there, see Theorem 3.7 below. This result is at the core of the main approach developed by OpenAI in [17], as is explained in the main body of the present paper. Shortly after and independently, Abbe and Montanari [1] adapted Franz and Leone’s technique for establishing a concentration property for the number of satisfying assignments when conditioned on the satisfiability of the formula. They also proved in the same paper that a concentration property stronger than one they managed to obtain would imply the validity of the -SAT conjecture. This is the approach successfully pursued by Carenini in [5]. A useful technical part of [1] was a variant of the superadditivity property which was also adapted by the OpenAI solution, see Proposition 3.10 below. A key novelty of the Carenini’s approach was obtaining a sharp bound on width of the Friedgut’s phase transition window.
The next major progress towards the full resolution of the conjecture was achieved in Ding, Sly and Sun [9, 10] who proved the validity of the conjecture for all sufficiently large values of . Their approach was based on very refined version of the second moment method and is technically quite involved. The upshot of this work was not only a positive resolution of the conjecture for large but also the validation of the phase transition values . These values were produced earlier in the statistical physics literature by Mertens, Mézard and Zecchina [16] also using the replica symmetry breaking method. It is worth mentioning that while the values produced by the replica symmetry breaking method have been confirmed in many papers such as [21] and [9, 10], the method itself remains a heuristic lacking a rigorous mathematical justification. The progress in [9, 10] which took place a decade ago was the last progress until the full resolution of the conjecture this year in [5] and [17].
Next we provide a brief outline of the proof. As in [4] a key technical object employed by the OpenAI proof is the concept of a frozen variable. A Boolean variable in the -SAT formula is defined to be frozen when the formula is satisfiable, but every satisfying solution fixes it as the same Boolean value, for example always at 0 or always at 1. The first technical step is then an upper bound on the number of frozen variables. As shown in Proposition 3.2, it is in expectation. This bound on the expected number of frozen variables is used next to obtain a bound on the variance of the hitting time associated with random formulas. The hitting time is a random variable defined by considering the random -SAT formula as a discrete time process indexed by , and constructed by adding one clause at a time. is then defined as largest value of for which the formula remains satisfiable, see Subsection 3.1. A bound on the expected number of frozen variables is used for obtaining an upper bound on the variance of , as stated in Proposition 3.5. The well-known Efron-Stein-SteeIe inequality Theorem 3.3 is used towards the proof of this bound. A direct application of Chebyshev’s inequality also implies concentration property of the hitting time , as stated in (7). The concentration of the hitting time property allows one to relate the expected value of the hitting time to its median value, namely the largest value of for which the likelihood of satisfiability is at least . This is the subject of Lemma 3.6. The log-superadditivity property established in [4] is then used for establishing superadditivity of the median times as articulated in Corollary 3.8. The final step in the proof is adaptation of the variant of the superadditivity property developed in [1]. This is the subject of Proposition 3.10 and this completes the description of the proof. Remarkably, as in the proof by Carenini in [5], the approach does not assume the validity of the Friedgut’s sharp transition property and instead obtains it as an immediate corollary. One should stress, however, that the scope of the applicability of Friedgut’s theorem is much broader than the random -SAT formula setting.
The remainder of the paper is organized as follows. The model description and the main theorem are stated in the next section. The proof of the main theorem is the subject of § 3, where the concepts of frozen variables and hitting times are introduced in the beginning. § 4 presents some remaining open questions.
Definitions and the main result
Consider Boolean variables , taking values 0 and 1. We fix which is clause size. A formula is a conjunction of some -clauses: where each clause is disjunction of of the variables or their negations . Thus for each there exists a subset (corresponding to variables without negation), and a subset (corresponding to negated variables), such that , and
We call the support of the clause . A formula is satisfiable if there exists a setting of the variables which satisfies the formula. Namely, if there exists a vector such that all clauses evaluate to 1 at this . Such a setting, when it exists, is called a satisfying assignment or a satisfying solution. We note that for each clause there exists only a single assignment of variables to values which do not satisfy the clause. When the formula is satisfiable we write . When it is not satisfiable we write .
A random formula with variables and clauses, denoted by , is obtained by generating the supports uniformly at random from all choices, and letting (and thus ) be chosen uniformly at random from choices as well, also independently from everything else. We denote by the probability that is sat: . The Satisfiability Conjecture asserted existence of a fixed threshold such that approaches 1 when stays uniformly smaller than , and approaches 0 when this ratio stays uniformly larger than , as diverges to infinity. The OpenAI paper [17] established precisely this which we now state as a formal theorem.
Theorem 2.1 (Theorem 1.1, [17]). For every there exists such that for every , and for every , .
As stated in the introduction, the sharp transition result of Friedgut [13] will not be used in the proof of Theorem 2.1. Conversely, it is an immediate implication of Theorem 2.1.
Proof of Theorem 2.1
Preliminaries
We begin by reducing the problem to the case of clauses generated with replacement. Specifically, consider a modified model of the random formula where replacement of variables is now allowed. Here a random clause is formed by selecting variables from the list independently and uniformly at random with replacement. The modified formula, denoted by (where wr stands for ”with replacement”), is then obtained by generating clauses with replacement independently, as in the original version. Let . We claim that it suffices to establish Theorem 2.1 with replacing . Specifically, suppose for every there exists such that for every , and for every , . Based on this assumption we now show the validity of Theorem 2.1 for the same limiting threshold . The validity of this claim follows from a standard fact from the theory of random graphs that the collisions stemming from possible replacements occur with probability bounded away from zero across the entire formula. Specifically, let (No-Collision) be the event that no single clause out of the clauses of the random formula contains repeated variables (with or without negation). For example, no clause can contain a variable twice or variables and simultaneously. It is straightforward to check that for every constant there exist such that . Furthermore, conditioned on the event , the formula is distributed as .
Now, fix any . Then
We have
By our assumption, the right-hand side converges to zero as . Since , we conclude .
Similarly, assume . Then
By our assumption . We conclude . This completes the proof of the claim.
The remainder of the paper is thus devoted to establishing Theorem 2.1 for replacing . For simplicity, we denote and by and , respectively, throughout the rest of the paper.
Next we introduce the concepts of hitting times and frozen variables. We begin by defining hitting times. Given and let denote the (random) number of solutions satisfying the formula . A straightforward computation shows . By Markov inequality . When , we obtain
for all sufficiently large . Define as the largest such that . Then . By the above for all . Let . Then for all , . In particular, . It is well known that for all , and thus for some and all
See for example [6] which shows that for , with high concentration around for the version without replacement. By the equivalence property above the same applies to the model with replacement. Finally, we use to assert (1).
Let be the hitting time defined as follows. Consider the random formula and the associated stochastic process . Define
Namely is the largest index of a clause which maintains the satisfiability property, capped at . Then for all we have . Thus is the median of the random variable and is median normalized by .
Next we define frozen variables. Given a formula defined on variables , a variable is called frozen if it takes the same value for all satisfying assignments. Namely , is frozen if either for all satisfying solutions , or for all satisfying solutions . If the formula is not satisfiable, (and thus the number of satisfying assignments is empty), the set of frozen variables is empty. Given a satisfiable formula and a clause note that the modified formula is not satisfiable if and only if every variable in the support of is frozen and its parity agrees with the value of the frozen variable. For example, if then is not satisfiable if and only if variables are frozen to values respectively.
Let denote the number of frozen variables in formula . We adopt the convention that when is not satisfiable. Note that for every formula , is precisely the probability that the modified formula is not satisfiable when is a -clause chosen uniformly at random. We write for short.
Controlling frozen variables
The goal of this subsection is to obtain an upper bound on the number of frozen variables in a random formula . In particular, we will establish in Proposition 3.2 below that the expected number of the frozen variables in formula is order on average when we average over the number of clauses in the range .
We begin with a preliminary lemma. It shows that, modulo order correction term, for every satisfiable formula , appending this formula with a clause chosen uniformly at random leads to a higher chance of maintaining satisfiability vs appending it with order many -clauses also chosen uniformly at random and independently.
Lemma 3.1. Let be any fixed formula on variables. Let be a -clause chosen uniformly at random and let be -clauses chosen independently uniformly at random. Suppose . There exists sufficiently large such that for all
Proof. The claim holds trivially when is not satisfiable. Thus assume is satisfiable. Suppose first . Then , and the claim holds trivially.
Thus suppose . Then
Then
where we use and for .
The following bound shows that for random formulas on variables the number of frozen variables is at most order “on average” when we average over in the range .
Proposition 3.2. For every there exists a constant and such that for all
Proof. Fix . By symmetry equals the probability that is satisfiable and the variable is frozen, since when is not satisfiable, by assumption. Let be the part of this formula spanned by the first variables . Consider the clauses containing the variable (where is random), so that . Consider the clauses , obtained from , by deleting variable . Each clause has at most variables. Specifically, the clause size is strictly less than if variable appears in more than once. Let be the event that all clauses , have size . We can find constant such that uniformly in .
::: Next, we make the following observation: if is a frozen variable in then is satisfiable (since is), but the formula obtained by appending is not satisfiable. That is , but . Indeed, otherwise a satisfying assignment of can be extended to a satisfying assignment of with either choice or , contradicting the assumption that is frozen. Thus
By earlier observation,
We now construct a sequence of modified formulas , starting with as follows. For , the formula is obtained from by removing clause and replacing it with -clauses on variables and their negations. These clauses are generated uniformly at random independently and also independently from the all the other clauses.
Fix $0\le d\le m$. We note that conditionally on , is distributed as . Applying Lemma 3.1 we have for some constant for all and for all $j=0,\ldots,d-1
Summing over we obtain that conditional on
On the other hand
We obtain
We note
We conclude
Summing over we obtain
for some dependent constant . Multiplying throughout by likelihood that we obtain
where subscript in emphasizes that the probability depends on . For fixed the random variable has Binomial distribution with trials and success probability . It is easy to see that . for some constant . Summing over , we obtain
and further using (4) we obtain
for some constant . Combining with (3) and (4) we complete the proof by increasing to absorb the additive constant .
Concentration of the hitting times
The goal of this subsection is to establish a very important technical result: the hitting time is concentrated around its expectation. Specifically, in Proposition 3.5 below we will show that the variance of is at most order . The concentration then will follow directly by applying Chebyshev’s inequality.
Given formula and index let denote the formula with clause omitted. Let be the corresponding hitting time. To be precise, let be the clauses of . Denote by the formula . Then
We omit index for brevity. Also we write for . Trivially for all . The following bound on the variance of is based on standard inequality known as Efron-Stein and Steele’s application of it to non-symmetric cases. We include the proof for completeness.
Theorem 3.3 (Efron-Stein-Steele bound). The following holds for all :
Proof. For denote by the -field generated by randomness of , where is assumed to be the trivial -field. Note that is measurable with respect to , since the realizations of , uniquely determine the formula and the value of as a result. Introduce martingale differences for
so that . A standard property satisfied by martingale differences is the orthogonality: for all . It is a simple consequence of the tower property for all . Orthogonality implies
Next, as does not depend on we have , which means
Applying the tower property we obtain
Applying conditional Jensen’s inequality . Combining with (5) we complete the proof.
The next lemma relates the variance of the hitting time to the expectation of the number of frozen variables.
Lemma 3.4. The following holds for every
Proof. Fix . Recall our earlier notation for . This is the formula obtained from the first clauses of the clauses of with clause omitted. Let be the same formula without omitting , so that is in distribution. Introduce the events
This is precisely the event . Then
We obtain
Next we claim that for every
Indeed, since then
On the other hand , the latter following from . This furnishes the other inclusion.
Consider the -field generated by clauses , , . The randomness of clauses as well as clauses is independent from this -field. Recall our notation . Then . Also implies for all . Similarly, we have for . The events and , are independent conditionally on , since they depend on randomness of disjoint clauses, namely and , . Thus
Then
Taking the outer expectation with respect to we obtain
Summing over and using (6) we conclude the proof.
We are ready to state and prove the concentration of hitting times property.
Proposition 3.5. For every there exists large enough constant such that for all . As a result for and
While and were simple to express in terms of , their detailed values are not of importance to the remainder of the proof. As we will see, it suffices to have and . The only adjustment is that the exponent appearing in Corollary 3.8 in the next subsection would need to be reduced to a smaller positive value.
Proof. The tail bound (7) follows from the bound on variance immediately by Chebyshev’s inequality. Thus we focus on bounding the variance . Using for all , we have
Applying Lemma 3.4 we obtain
Applying Proposition 3.2 we obtain
Finally, using Efron-Stein-Steele bound Theorem 3.3 we obtain
This completes the proof by setting .
From concentration of to superadditivity of the normalized medians
The main technical result for this section is establishing the superadditivity type property for the normalized median times which is subject of Corollary 3.8, as well as continuity of the median times in . Specifically, in Lemma 3.9 we establish that is close to . We begin by showing the proximity of mean and median of the hitting times.
Lemma 3.6. Let be as in Proposition 3.5. There exists such that for all
As we will see in the proof, the choice of multiplier 2 is somewhat arbitrary and any constant strictly larger than 1 suffices.
Proof. Suppose first . Then by Proposition 3.5 . On the other hand
implying
for large enough which is a contradiction. We conclude .
Conversely, suppose . Then . On the other hand
which is again a contradiction when . We conclude .
Next we import the following superadditivity result from [4] based on the combinatorial interpolation technique. We reproduce the proof for completeness. This result is at the core of establishing the satisfiability limit as stated in our main result, Theorem 2.1.
Theorem 3.7. Given such that and given , let random variables have Poisson distributions with means , respectively. Then
where the expectations of and , are with respect to the randomness of , .
Proof. Consider the random formula . On the event we consider the following process indexed by time . We order clauses uniformly at random and independently from any other randomness of the formula. For each we delete the -th clause . We then generate a new -clause as follows. With probability this clause is generated uniformly at random with replacement from the set of variables and their negations. With the remaining probability the clause is generated uniformly at random with replacement from the set of variables and their negations. If we do nothing. Let , be the random formula obtained at time , after clause is deleted and is created. In particular, . Also by the Poisson splitting theorem, the formula at the end of the process is a disjoint union of independent formulas , on the two sets of nodes and , respectively, where is distributed as for .
Fix and condition on . We claim that for every
from which the assertion of the theorem follows.
Let be the random formula obtained after deleting clause but before adding the clause . Then and . We condition on the realization of . Note that and are independent from . Assume first is satisfiable formula. Then
For , let be the number of frozen variables of the formula in subsets and , respectively. Then
Using the convexity of the function when restricted to the domain , the right-hand side is at least
We conclude . On the other hand, when formula is not satisfiable, we have . We conclude that for every realization of , . Thus (8) is verified. Removing the conditioning on and we complete the proof. ∎
The key implication of Theorem 3.7 is the following property of the normalized median times.
Corollary 3.8. There exists such that for all
Proof. Fix and let . Let . Set . Then . (We note that are not necessarily integers, unlike , ,) Let , be Poisson random variables with means , respectively. We use the following universal lower bound for a Poisson random variable with mean : . This implies for
Applying Theorem 3.7, we obtain . Fix . This is possible since for all . Since , by Chebyshev’s inequality we have
Thus
namely
Since , applying the bound (1) on , this is at least for large enough. Then applying the concentration bound (7), for large enough . Applying Lemma 3.6 we conclude provided is large enough. Dividing by we obtain for sufficiently large
concluding the proof.
Next we lower bound in terms of .
Lemma 3.9. There exists such that for all
Proof. Let be the number of clauses containing variable in . For we have . In fact has a Poisson distribution in the limit with independent parameter, but this will not be explicitly needed. We have . Thus for every
Applying this to
We claim that for sufficiently large and all , . Indeed, otherwise
which is violated when and is large enough. Combining with Lemma 3.6 we obtain
Dividing by and using , which holds for sufficiently large and by (1), we obtain the result.
From superadditivity to the existence of a limit of normalized medians . Proof of the main theorem
We complete the proof of the main theorem in this section by establishing the existence of a limit of normalized medians using the near superadditivity property. The following variant of the superadditivity property is adopted from Abbe and Montanari [1].
Proposition 3.10. Suppose , is a non-negative bounded sequence of real values satisfying the following properties. There exists and such that for all
and for all
Then for all and all
As a result the limit exists.
We first show how this claim implies the main theorem.
Proof of Theorem 2.1. Corollary 3.8 and Lemma 3.9 imply that our sequence satisfies the assumptions of the Proposition 3.10 with chosen as in Proposition 3.5. Thus the limit exists. By (1) we have . Fix any such that . By Lemma 3.6 we can find large enough such that for all . Again taking sufficiently large we obtain for all
Take . Then applying the concentration bound Proposition 3.5 for large enough and all
Here we used the uniform bound (1) on . Thus and the one side of the assertion of the theorem is established.
The other side is established similarly. Taking sufficiently large we obtain for all
We set . Then
Thus , and the other side of the assertion of the theorem is established. □
Thus it remains to prove Proposition 3.10.
Proof of Proposition 3.10. The existence of the limit is immediate from (13). Thus we focus on proving (13).
Given any positive integer consider a binary tree constructed recursively as follows. Every node of this tree is marked with a positive integer denoted by . The root of the tree is marked with value itself. When the associated tree is a single node , with . Assuming the tree is defined for all , we construct it for recursively as follows. The root of the tree has two children . Suppose is even. Then the subtrees emanating from both , are . In particular, . On the other hand, when is odd, the two children , of the root of are roots of subtrees and , respectively. In particular, the two children and are marked with and , respectively. As a result, the leaves of every tree are marked with value . Since in either even or odd case we have , the depth of the tree is logarithmic in , though this fact will not be required for the remainder of the proof.
Now, fix any and . Finding , such that , we can write . Note . We assume . The case is treated similarly, and the proof is omitted. Applying (11) with and we have
Now consider the two binary trees and defined as above. Starting from the left tree with the root marked with , apply (11) recursively down the tree until the leaves of the left tree are reached. For example, in the first step, assuming is even we obtain
Assuming, on the other hand, is odd, in the first step we obtain instead
Iterating we obtain
where is the additive correction accumulated across a path from the root to a leaf. From the relation between a mark of a node and the mark of any of its child, that we observed above, every next correction term up the path is at most times the previous correction term. The largest correction is associated with leaves and is . Thus we obtain
We obtain
Similarly, we obtain
Applying (12) we obtain
Applying this to (14) we obtain
completing the proof.
Some open questions
Several questions appear to be within the reach of the current techniques, in particular ones developed in [5] and [17]. In particular, it seems very plausible that the approach extends to other models of random constraint satisfaction problems such as proper coloring of a graph.
Furthermore, while the validity of the limiting satisfiability threshold is now established, it is not known whether it coincides with ground state energy limit, the existence of which was established in [4]. Specifically, it is shown in [4] that for every fixed value , the minimum number of violated clauses in the random formula converges to some limit when normalized by . Define as . is strictly positive since is zero with high probability when . What remains unclear, though is extremely plausible, is whether . Specifically, at the present stage, we cannot rule out a range of values above for which on the one hand the formula is not satisfiable with high probability, but on the other hand solutions exist which violate only sublinearly in many clauses also with high probability. Provided an exponential concentration of the hitting time around its expectation holds, such a conclusion would be an immediate corollary of Theorem 2.1 and the log-superadditivity property Theorem 3.7 from [4]. Unfortunately, the current concentration bound from Proposition 3.5 is too weak for this purpose.
Finally, unfortunately not all random constraint satisfaction problems such as random -SAT and spin glasses are amenable to the interpolation technique. The key challenge is that the convexity property such as one in (9) and (10) does not always hold. A notable counter-example is the Minimum Bisection problem in sparse random graph, see [15] for the definition and some partial results. Specifically, given a sparse Erdős-Rényi graph let be its minimum bisection value. The expectation of this value is trivially and it is natural to conjecture that the limit exists. Unfortunately, the counterparts of the expressions (9) and (10) for the Minimum Bisection problem do not exhibit the convexity property. As a result the validity of the conjecture remains open.
References
- [1]Emmanuel Abbe and Andrea Montanari, On the concentration of the number of solutions of random satisfiability formulas, Random Structures & Algorithms 45 (2014), no. 3, 362–382.arxiv.org/abs/1006.3786
- [2]D. Achlioptas and Y. Peres, The threshold for random k-SAT is 2ᵏ ln 2 − O(k), Proc. 45th Ann. Symposium on the Theory of Computing (2003).
- [3]D. Achlioptas and G. Sorkin, Optimal myopic algorithms for random 3-SAT, Proc. 41st IEEE Symposium on Foundations of Computer Science (2000).
- [4]M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, Annals of Probability. (Conference version in Proc. 42nd Ann. Symposium on the Theory of Computing (STOC) 2010) 41 (2013), 4080–4115.
- [5]G. Carenini, A polynomial scaling window for random k-sat and a proof of the satisfiability conjecture, Electronic Colloquium on Computational Complexity, Report No. 229. https://eccc.weizmann.ac.il/report/2026/229/ (2026).
- [6]V. Chvatal and B. Reed, Mick gets some (the odds are on his side), Proc. 33d Symposium on Foundations of Computer Science (1992).
- [7]Vašek Chvátal and Bruce Reed, Mick gets some (the odds are on his side)(satisfiability), Proceedings., 33rd Annual Symposium on Foundations of Computer Science, IEEE, 1992, pp. 620–627.DOI
- [8]Amin Coja-Oghlan and Konstantinos Panagiotou, The asymptotic k-SAT threshold, Advances in Mathematics 288 (2016), 985–1068.
- [9]Jian Ding, Allan Sly, and Nike Sun, Proof of the satisfiability conjecture for large k, Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 59–68.
- [10]———, Proof of the satisfiability conjecture for large k, Annals of Mathematics 196 (2022), no. 1, 1–388.
- [11]F.Guerra and F.L.Toninelli, The thermodynamic limit in mean field spin glass models, Commun. Math. Phys. 230 (2002), 71–79.
- [12]S. Franz and M. Leone, Replica bounds for optimization problems and diluted spin systems, Journal of Statistical Physics 111 (2003), no. 3/4, 535–564.arxiv.org/abs/cond-mat/0208280
- [13]E. Friedgut, Sharp thresholds of graph properties, and the k-SAT problem, J. Amer. Math. Soc. 4 (1999), 1017–1054.DOI
- [14]Francesco Guerra, Broken replica symmetry bounds in the mean field spin glass model, Communications in mathematical physics 233 (2003), 1–12.DOI
- [15]Brice Huang, Convergence of maximum bisection ratio of sparse random graphs, Electronic Communications in Probability 23 (2018), 1–10.DOI
- [16]Stephan Mertens, Marc Mézard, and Riccardo Zecchina, Threshold values of random k-sat from the cavity method, Random Structures & Algorithms 28 (2006), no. 3, 340–373.
- [17]OpenAI, A limiting satisfiability threshold for every fixed clause size, https://github.com/openai/math/blob/main/preprints/ (2026).
- [18]Dmitry Panchenko, The Sherrington-Kirkpatrick model, Springer Science & Business Media, 2013.DOI
- [19]Giorgio Parisi, Infinite number of order parameters for spin-glasses, Physical Review Letters 43 (1979), no. 23, 1754.
- [20]———, A sequence of approximated solutions to the SK model for spin glasses, Journal of Physics A: Mathematical and General 13 (1980), no. 4, L115.
- [21]Michel Talagrand, The Parisi formula, Annals of mathematics (2006), 221–263.