On the thresholds in linear and nonlinear Boolean equations
From MaRDI portal
Publication:614622
DOI10.1140/epjb/e2010-00173-7zbMath1202.82031OpenAlexW2152807979MaRDI QIDQ614622
Publication date: 4 January 2011
Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1140/epjb/e2010-00173-7
Phase transitions (general) in equilibrium statistical mechanics (82B26) Boolean functions (06E30) Theory of computing (68Q99)
Cites Work
- Unnamed Item
- The SAT-UNSAT transition for random constraint satisfaction problems
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- The cavity method at zero temperature
- Differential equations for random processes and random graphs
- On the dynamics of the glass transition on Bethe lattices
- On the freezing of variables in random constraint satisfaction problems
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Information, Physics, and Computation
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Sharp thresholds of graph properties, and the $k$-sat problem
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Survey propagation: An algorithm for satisfiability
- Determining computational complexity from characteristic ‘phase transitions’
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Threshold values of random K‐SAT from the cavity method
- Rigorous results for random (\(2+p)\)-SAT
- Lower bounds for random 3-SAT via differential equations
