On the constraint length of random \(k\)-CSP

DOI10.1007/s10878-014-9731-3zbMath1326.90074MaRDI QIDQ2352362

Zong Sheng Gao, Jun Liu, Guangyan Zhou

Publication date: 1 July 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9731-3

zbMATH Keywords

phase transition; threshold phenomena; second moment method; \(k\)-CSP

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, Bounding the scaling window of random constraint satisfaction problems, Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, The scaling window of the model \(d\)-\(k\)-CSP

Cites Work

• Unnamed Item
• A note on random \(k\)-SAT for moderately growing \(k\)
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Formula dissection: A parallel algorithm for constraint satisfaction
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Many hard examples in exact phase transitions
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Random constraint satisfaction: A more accurate picture