On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
From MaRDI portal
Publication:955013
DOI10.1016/j.tcs.2008.06.053zbMath1152.68052OpenAlexW2001001966WikidataQ125756943 ScholiaQ125756943MaRDI QIDQ955013
Alistair Sinclair, Elitza Maneva
Publication date: 18 November 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.053
Related Items
Upper-bounding the \(k\)-colorability threshold by counting covers, The asymptotic \(k\)-SAT threshold, The cook-book approach to the differential equation method, Using sequential runtime distributions for the parallel speedup prediction of SAT local search, On the satisfiability threshold of formulas with three literals per clause, Satisfiability threshold for random regular \textsc{nae-sat}, Pruning processes and a new characterization of convex geometries, Estimating satisfiability, Large-scale parallelism for constraint-based local search: the costas array case study
Cites Work
- Unnamed Item
- Unnamed Item
- Pruning processes and a new characterization of convex geometries
- The unsatisfiability threshold revisited
- Survey propagation as local equilibrium equations
- Almost all graphs with 1.44n edges are 3-colorable
- A new look at survey propagation and its generalizations
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Bounding the unsatisfiability threshold of random 3-SAT
- Tail bounds for occupancy and the satisfiability threshold conjecture
- The probabilistic analysis of a greedy satisfiability algorithm
- On the solution-space geometry of random constraint satisfaction problems
