On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
type: Item
instance of: scholarly article
title: On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
zbMATH Open document ID: 1152.68052
author: Elitza Maneva
author: Alistair Sinclair
published in: Theoretical Computer Science
publication date: 2008-11-18T00:00:00Z
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5368343
zbMATH Keywords: random 3-SAT
zbMATH Keywords: phase transitions
zbMATH Keywords: survey propagation
zbMATH Keywords: threshold of satisfiability
zbMATH Keywords: first-moment method
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.06.053
OpenAlex ID: W2001001966
Wikidata QID: Q125756943
cites work: On the solution-space geometry of random constraint satisfaction problems
cites work: Pruning processes and a new characterization of convex geometries
cites work: Survey propagation as local equilibrium equations
cites work: Almost all graphs with 1.44n edges are 3-colorable
cites work: A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
cites work: Q4952608
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Bounding the unsatisfiability threshold of random 3-SAT
cites work: Tail bounds for occupancy and the satisfiability threshold conjecture
cites work: The probabilistic analysis of a greedy satisfiability algorithm
cites work: The unsatisfiability threshold revisited
cites work: Approximating the unsatisfiability threshold of random formulas
cites work: A new look at survey propagation and its generalizations
cites work: Q4237477
DOI: 10.1016/J.TCS.2008.06.053
description: scientific article; zbMATH DE number 5368343