On the concentration of the number of solutions of random satisfiability formulas

DOI10.1002/rsa.20501zbMath1373.68300arXiv1006.3786OpenAlexW2107779545MaRDI QIDQ2930051

Emmanuel Abbe, Andrea Montanari

Publication date: 17 November 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.3786

zbMATH Keywords

countingsharp thresholdsatisfiabilityinterpolation methodconstraint satisfaction problemsconcentration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Random \(\mathbb{Z}^d\)-shifts of finite type, Counting Solutions to Random CNF Formulas, The number of satisfying assignments of random 2‐SAT formulas, Threshold saturation in spatially coupled constraint satisfaction problems, Right-convergence of sparse random graphs, Optimal testing for planted satisfiability problems, The number of solutions for random regular NAE-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Bounds for diluted mean-fields spin glass models
• The thermodynamic limit in mean field spin glass models
• Replica bounds for optimization problems and diluted spin systems
• The relative complexity of approximate counting problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Tight Bounds for LDPC and LDGM Codes Under MAP Decoding
• Information, Physics, and Computation
• The Complexity of Enumeration and Reliability Problems
• Sharp thresholds of graph properties, and the $k$-sat problem
• Two‐coloring random hypergraphs
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Sharp Bounds for Optimal Decoding of Low-Density Parity-Check Codes
• Determining computational complexity from characteristic ‘phase transitions’
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Replica bounds for diluted non-Poissonian spin systems
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• On the solution‐space geometry of random constraint satisfaction problems
• Random 2-SAT: Results and problems