The scaling window of the model \(d\)-\(k\)-CSP

DOI10.1016/j.jmaa.2015.09.015zbMath1334.82035MaRDI QIDQ890505

Guangyan Zhou, Jun Liu, Zong Sheng Gao

Publication date: 10 November 2015

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jmaa.2015.09.015

zbMATH Keywords

phase transition; constraint satisfaction problem; finite-size scaling; the second moment method

Mathematics Subject Classification ID

82B26: Phase transitions (general) in equilibrium statistical mechanics

Related Items

On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• A general model and thresholds for random constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• Generalized satisfiability problems: Minimal elements and phase transitions.
• The 3-XORSAT threshold.
• A sharp threshold for a random constraint satisfaction problem
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• On the constraint length of random \(k\)-CSP
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• The scaling window of the 2-SAT transition
• Models for Random Constraint Satisfaction Problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Random constraint satisfaction: A more accurate picture
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems