On the $K$-sat model with large number of clauses

Abstract

We show that in the $K$-sat model with $N$ variables and $\alpha N$ clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is $\alpha /2^K-\sqrt{\alpha }{c}_{\ast }(N)/2^K$ up to smaller order terms $o(\sqrt{\alpha })$ as $\alpha \to \infty$ uniformly in $N$, where $c_{\ast }(N)$ is the expected normalized maximum energy of some specific mixed $p$-spin spin glass model. The formula for the limit of $c_{\ast }(N)$ is well known in the theory of spin glasses.

References in corpus (3)

• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• Disorder chaos in some diluted spin glass models

Cited by in corpus (3)

• The marginally stable Bethe lattice spin glass revisited
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• Disorder chaos in some diluted spin glass models