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

DOI10.1080/00207160903193970MaRDI QIDQ5850753zbMATH OpenOpenAlexFDO

Authors Gabriel 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

\(\epsilon\)-1-in-\(k\) SAToverlapsphase transitionrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• The number of satisfying assignments of random regular k-SAT formulas
• On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
• The structure of the set of satisfying assignments for a random \(k\)-CNF
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• scientific article; zbMATH DE number 1929945
• On the critical exponents of random k‐SAT

Cites work

• Component structure in the evolution of random hypergraphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 5018174 (Why is no real title available?)
• Models and thresholds for random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Phase Transitions in Combinatorial Optimization Problems
• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• The phase transition in 1-in-k SAT and NAE 3-SAT

Cited in

(1)

• Tricritical points in random combinatorics: the -SAT case

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

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