Geometric properties of satisfying assignments of random ε-1-in-kSAT

DOI10.1080/00207160903193970zbMath1185.68361OpenAlexW1542618503MaRDI QIDQ5850753

Gabriel I. Istrate

Publication date: 15 January 2010

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160903193970

zbMATH Keywords

phase transitionrandom graphsoverlaps\(\epsilon\)-1-in-\(k\) SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Critical phenomena in equilibrium statistical mechanics (82B27) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• Component structure in the evolution of random hypergraphs
• Models and thresholds for random constraint satisfaction problems
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Phase Transitions in Combinatorial Optimization Problems
• On the solution-space geometry of random constraint satisfaction problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Geometric properties of satisfying assignments of random ε-1-in-kSAT