Models and thresholds for random constraint satisfaction problems

DOI10.1145/509907.509941MaRDI QIDQ3579225zbMATH OpenOpenAlexFDO

Authors

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/509907.509941

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cited in

(16)

• Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
• Geometric properties of satisfying assignments of random ε-1-in-kSAT
• List coloring triangle-free hypergraphs
• Acyclic edge colourings of graphs with large girth
• Hunting for sharp thresholds
• Resolution complexity of random constraint satisfaction problems: Another half of the story
• An algorithm for random signed 3-SAT with intervals
• A general model and thresholds for random constraint satisfaction problems
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Bounding the scaling window of random constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• On Random Ordering Constraints
• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• Threshold properties of random Boolean constraint satisfaction problems
• Generalized satisfiability problems: Minimal elements and phase transitions.

This page was built for publication: Models and thresholds for random constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579225)