Geometrical organization of solutions to random linear Boolean equations

DOI10.1088/1742-5468/2006/10/P10007zbMath1456.94146OpenAlexW1991431422MaRDI QIDQ4968895

Thierry Mora, Marc Mézard

Publication date: 9 July 2019

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1088/1742-5468/2006/10/p10007

zbMATH Keywords

message-passing algorithmscavity and replica methodtypical-case computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Quantum dynamics and nonequilibrium statistical mechanics (general) (82C10) Dynamic and nonequilibrium phase transitions (general) in statistical mechanics (82C26) Boolean functions (94D10)

Related Items

Pairs of SAT-assignments in random Boolean formulæ

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The 3-XORSAT threshold.
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Coloring Random Graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• The intractability of computing the minimum distance of a code
• Optimization problems and replica symmetry breaking in finite connectivity spin glasses
• Factor graphs and the sum-product algorithm
• Finite-length analysis of low-density parity-check codes on the binary erasure channel
• Statistical Physics of Spin Glasses and Information Processing
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Theory and Applications of Satisfiability Testing