Random Formulas Have Frozen Variables

DOI10.1137/070680382zbMath1185.68508OpenAlexW1996338626MaRDI QIDQ5189545

Federico Ricci-Tersenghi, Demetrios Achlioptas

Publication date: 17 March 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3abf7b1c2d7e4ca6c39246692905d97b8d0aeb65

zbMATH Keywords

phase transitionssatisfiabilityrandom formulasfrozen variables

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Phase transitions (general) in equilibrium statistical mechanics (82B26) Discrete mathematics in relation to computer science (68R99)

Related Items (11)

Completeness Results for Counting Problems with Easy Decision ⋮ On the solution‐space geometry of random constraint satisfaction problems ⋮ Maximum independent sets on random regular graphs ⋮ The asymptotic \(k\)-SAT threshold ⋮ Leveraging cluster backbones for improving MAP inference in statistical relational models ⋮ The cook-book approach to the differential equation method ⋮ Organization mechanism and counting algorithm on vertex-cover solutions ⋮ The Decimation Process in Random k-SAT ⋮ Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical Distributions ⋮ The solution space geometry of random linear equations ⋮ Biased landscapes for random constraint satisfaction problems

This page was built for publication: Random Formulas Have Frozen Variables