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

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.

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)

Cites Work

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

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)