The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
read the original abstract
We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and sets) a variable depending on its degree and that of its complement.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Optimal Phylogenetic Reconstruction from Sampled Quartets
An efficient algorithm recovers phylogenetic trees from Θ(n) noisy quartets under random classification noise, matching the information-theoretic lower bound and achieving near-optimal quartet distance.
-
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
Triplet constraints realizable in D-dimensional Euclidean space cannot be preserved above 50% accuracy by any embedding of dimension at most cD for constant c<1, with UGC-hardness preventing better polynomial-time sol...
-
Computational Phase Transition Signature in Gibbs Sampling
Computational phase transitions in decision problems exhibit a detectable signature in Gibbs distributions that can be observed in physical annealing processors.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.