Geometrical organization of solutions to random linear Boolean equations

DOI10.1088/1742-5468/2006/10/P10007zbMATH Open1456.94146OpenAlexW1991431422MaRDI QIDQ4968895FDOQ4968895

Authors 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

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

Recommendations

• Inside the clustering window for random linear equations
• The set of solutions of random XORSAT formulae
• The set of solutions of random XORSAT formulae
• The solution space geometry of random linear equations
• The 3-XORSAT threshold.

Cites Work

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

Cited In (7)

• Pairs of SAT-assignments in random Boolean formulæ
• On the thresholds in linear and nonlinear Boolean equations
• Counting and hardness-of-finding fixed points in cellular automata on random graphs
• Geometry of the Poisson Boolean model on a region of logarithmic width in the plane
• The set of solutions of random XORSAT formulae
• The solution space geometry of random linear equations
• Inside the clustering window for random linear equations

This page was built for publication: Geometrical organization of solutions to random linear Boolean equations

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