Random formulas have frozen variables

DOI10.1137/070680382MaRDI QIDQ5189545zbMATH OpenOpenAlexFDO

Authors Federico Ricci-Tersenghi, D. 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

frozen variablesphase transitionsrandom formulassatisfiability

Mathematics Subject Classification ID

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

Recommendations

• Solution clustering in random satisfiability
• Frozen variables in random Boolean constraint satisfaction problems
• On the freezing of variables in random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems

Cited in

(17)

• Leveraging cluster backbones for improving MAP inference in statistical relational models
• Maximum independent sets on random regular graphs
• Satisfiability by Maxwell-Boltzmann and Bose-Einstein statistical distributions
• The decimation process in random k-SAT
• Organization mechanism and counting algorithm on vertex-cover solutions
• The large deviations of the whitening process in random constraint satisfaction problems
• The cook-book approach to the differential equation method
• The solution space geometry of random linear equations
• Biased landscapes for random constraint satisfaction problems
• Completeness results for counting problems with easy decision
• Frozen variables in random Boolean constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Reasoning with propositional logic: from SAT solvers to knowledge compilation
• Counting and hardness-of-finding fixed points in cellular automata on random graphs
• Recognizing frozen variables in constraint satisfaction problems
• The asymptotic k-SAT threshold
• Solution clustering in random satisfiability

This page was built for publication: Random formulas have frozen variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189545)