The large deviations of the whitening process in random constraint satisfaction problems

DOI10.1088/1742-5468/2016/05/053401zbMath1459.90135arXiv1602.01700OpenAlexW2264900195MaRDI QIDQ3302666

Luca Dall'Asta, Alfredo Braunstein, Lenka Zdeborová, Guilhem Semerjian

Publication date: 11 August 2020

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Stochastic programming (90C15) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Related Items (7)

Phase transitions in theq-coloring of random hypergraphs ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Optimization of the dynamic transition in the continuous coloring problem ⋮ Walksat Stalls Well Below Satisfiability

Uses Software

• ChainSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Upper-bounding the \(k\)-colorability threshold by counting covers
• The set of solutions of random XORSAT formulae
• Average time analyses of simplified Davis-Putnam procedures
• Corrigendum to ``Average time analyses of simplified Davis-Putnam procedures
• Reconstruction of random colourings
• On large deviation properties of Erdős-Rényi random graphs
• Properties of atypical graphs from negative complexities
• Reconstruction on trees and spin glass transition
• Rigorous inequalities between length and time scales in glassy systems
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• The cavity method at zero temperature
• Minimal contagious sets in random regular graphs
• On the dynamics of the glass transition on Bethe lattices
• On the freezing of variables in random constraint satisfaction problems
• Pairs of SAT-assignments in random Boolean formulæ
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Survey propagation as local equilibrium equations
• Optimizing spread dynamics on graphs by message passing
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• A new look at survey propagation and its generalizations
• Information, Physics, and Computation
• Sharp thresholds of graph properties, and the $k$-sat problem
• Factor graphs and the sum-product algorithm
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The Decimation Process in Random $k$-SAT
• The solution space geometry of random linear equations
• Reducibility among Combinatorial Problems
• The asymptotic k-SAT threshold
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Better Algorithm for Random k-SAT
• Catching the k-NAESAT threshold
• The freezing threshold for k-colourings of a random graph
• Threshold values of random K‐SAT from the cavity method
• The complexity of theorem-proving procedures
• Bicolouring random hypergraphs
• Frozen variables in random boolean constraint satisfaction problems
• The condensation transition in random hypergraph 2-coloring
• On the solution-space geometry of random constraint satisfaction problems
• Almost all graphs with average degree 4 are 3-colorable
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Lower bounds for random 3-SAT via differential equations
• Upper bounds on the satisfiability threshold
• Satisfiability threshold for random regular \textsc{nae-sat}

This page was built for publication: The large deviations of the whitening process in random constraint satisfaction problems