On the -sat model with large number of clauses
arXiv:1608.06256
Abstract
We show that in the -sat model with variables and clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is up to smaller order terms as uniformly in , where is the expected normalized maximum energy of some specific mixed -spin spin glass model. The formula for the limit of is well known in the theory of spin glasses.
References in corpus (6)
- The Bethe lattice spin glass revisited
- Extremal Cuts of Sparse Random Graphs
- Spin glass models from the point of view of spin distributions
- A connection between MAX -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