Current tightest bounds for critical 3-SAT density

Question

I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable. (Here $\epsilon$ is any small constant and $n$ is the number of variables.) If the number is $(\alpha - \epsilon) n$ or less, they are almost surely satisfiable.

The thesis Belief propagation algorithms for constraint satisfaction problems by Elitza Nikolaeva Maneva challenges the problem from the angle of belief propagation known in information theory. On page 13, it says $3.52<\alpha<4.51$ if $\alpha$ exists.

What are the best known bounds for $\alpha$?

Answer 1

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.

The unsatisfiability threshold is known to be at most 4.4898, a slight improvement since Maneva's 2001 thesis.

• J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz. On the satisfiability threshold of formulas with three literals per clause, Theoretical Computer Science 410, 2009, 2920–2934. doi:10.1016/j.tcs.2009.02.020 (preprint from one of the authors)

The satisfiability threshold is known to be at least 3.52, which is unchanged from the time of Maneva's thesis.

• A. C. Kaporis, L. M. Kirousis, E. G. Lalas. The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Random Structures and Algorithms 28, 2006, 444–480. doi:10.1002/rsa.20104

These bounds were recently cited by Achlioptas and Menchaca-Mendez as the best known to date.

• D. Achlioptas, R. Menchaca-Mendez. Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method, ICALP 2012, LNCS 7391, 1–12. doi:10.1007/978-3-642-31594-7_1

Answer 2

There is a new 58 page paper (32 refs) accepted to STOC 2013,

Going after the k-SAT threshold by Coja-Oghlan and Konstantinos Panagiotou

that surveys and advances the area of determining the precise k-SAT threshhold, building especially from results borrowed from statistical physics. From the abstract:

Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the k-SAT threshold up to an additive $\ln 2 − {1 \over 2} +O(1/k) \approx 0.19$.

Coja-Oghlan, Amin; Panagiotou, Konstantinos, Going after the $k$-SAT threshold, Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 705-714 (2013). ZBL1293.68164.