The replica symmetric phase of random constraint satisfaction problems

DOI10.1017/S0963548319000440zbMath1504.68152arXiv1802.09311OpenAlexW3098834697MaRDI QIDQ4993097

Amin Coja-Oghlan, Noela Müller, Tobias Kapetanopoulos

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Phase transitions (general) in equilibrium statistical mechanics (82B26) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Related Items

Strong replica symmetry in high-dimensional optimal Bayesian inference, The number of satisfying assignments of random 2‐SAT formulas, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper-bounding the \(k\)-colorability threshold by counting covers
• Reconstruction and estimation in the planted partition model
• A threshold for unsatisfiability
• Reconstruction for the Potts model
• On the Potts antiferromagnet on random graphs
• The asymptotic \(k\)-SAT threshold
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The 3-XORSAT threshold.
• Information-theoretic thresholds from the cavity method
• Charting the replica symmetric phase
• Constraining the clustering transition for colorings of sparse random graphs
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• Foundations of quantization for probability distributions
• The satisfiability threshold for random linear equations
• On the chromatic number of a random hypergraph
• Random Graphs and Complex Networks
• Proof of the Satisfiability Conjecture for Large k
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Harnessing the Bethe free energy
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• The solution of some random NP-hard problems in polynomial expected time
• Candidate One-Way Functions Based on Expander Graphs
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• The Number of Satisfying Assignments of Random Regulark-SAT Formulas
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Quantization for Probability Measures in the Prokhorov Metric
• Relations between average case complexity and approximation complexity
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Information, Physics, and Computation
• Almost all cubic graphs are Hamiltonian
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• Algebraic Attacks against Random Local Functions and Their Countermeasures
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• On the Number of Solutions in Random Graphk-Colouring
• Hypergraph coloring up to condensation
• Semirandom Models as Benchmarks for Coloring Algorithms
• Rigid Colorings of Hypergraphs and Contiguity
• The Satisfiability Threshold fork-XORSAT
• Planting Colourings Silently
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The complexity of satisfiability problems
• Catching the k-NAESAT threshold
• The freezing threshold for k-colourings of a random graph
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• The condensation transition in random hypergraph 2-coloring
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Limits of local algorithms over sparse random graphs
• The two possible values of the chromatic number of a random graph
• Satisfiability threshold for random regular \textsc{nae-sat}
• The condensation phase transition in random graph coloring