On the thresholds in linear and nonlinear Boolean equations

DOI10.1140/EPJB/E2010-00173-7MaRDI QIDQ614622zbMATH OpenOpenAlexFDO

Authors Sumit K. Garg

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

Mathematics Subject Classification ID

Boolean functions (06E30) Theory of computing (68Q99) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Recommendations

• Geometrical organization of solutions to random linear Boolean equations
• Phase transition in a system of random sparse Boolean equations
• The 3-XORSAT threshold.
• Inside the clustering window for random linear equations
• Approximating the Satisfiability Threshold for Random k-XOR-formulas

Cites work

• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Determining computational complexity from characteristic ``phase transitions
• Differential equations for random processes and random graphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 2153834 (Why is no real title available?)
• Information, Physics, and Computation
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Lower bounds for random 3-SAT via differential equations
• On the dynamics of the glass transition on Bethe lattices
• On the freezing of variables in random constraint satisfaction problems
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Rigorous results for random (2+p)-SAT
• Sharp thresholds of graph properties, and the k-sat problem
• Survey propagation: An algorithm for satisfiability
• The cavity method at zero temperature
• The SAT-UNSAT transition for random constraint satisfaction problems
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(3)

• Phase transition in a system of random sparse Boolean equations
• Boolean trends in linear inequalities
• Statistical and algebraic analysis of a family of random Boolean equations

This page was built for publication: On the thresholds in linear and nonlinear Boolean equations

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