Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
From MaRDI portal
Publication:3446816
DOI10.1137/S0097539703434231zbMath1120.68096arXivcond-mat/0310227OpenAlexW2088419249MaRDI QIDQ3446816
Moore, Cristopher, Demetrios Achlioptas
Publication date: 26 June 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cond-mat/0310227
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (61)
Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ Phase transitions in discrete structures ⋮ The list chromatic number of graphs with small clique number ⋮ The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ Satisfiability Thresholds beyond k −XORSAT ⋮ A topological dynamical system with two different positive sofic entropies ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Information-theoretic thresholds from the cavity method ⋮ Random k -SAT and the power of two choices ⋮ On the number of solutions in random hypergraph 2-colouring ⋮ Limits of discrete distributions and Gibbs measures on random graphs ⋮ On the concentration of the chromatic number of a random hypergraph ⋮ A concentration inequality for the facility location problem ⋮ On the thresholds in linear and nonlinear Boolean equations ⋮ Harnessing the Bethe free energy ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Biased random k‐SAT ⋮ The discrepancy of random rectangular matrices ⋮ Digital collections of examples in mathematical sciences ⋮ Panchromatic 3-coloring of a random hypergraph ⋮ Panchromatic 3-colorings of random hypergraphs ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ On the structure of the set of panchromatic colorings of a random hypergraph ⋮ Random 2 XORSAT phase transition ⋮ The asymptotic \(k\)-SAT threshold ⋮ On Random Betweenness Constraints ⋮ Tractability from overparametrization: the example of the negative perceptron ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem ⋮ On panchromatic colourings of a random hypergraph ⋮ Two-Colorings of a Random Hypergraph ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ The Decimation Process in Random k-SAT ⋮ Charting the replica symmetric phase ⋮ Charting the replica symmetric phase ⋮ Panchromatic colorings of random hypergraphs ⋮ The satisfiability threshold for random linear equations ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Optimal testing for planted satisfiability problems ⋮ Spin systems on Bethe lattices ⋮ Unnamed Item ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ Random 2-XORSAT at the Satisfiability Threshold ⋮ Independent Sets in Random Graphs from the Weighted Second Moment Method ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ The probabilistic analysis of a greedy satisfiability algorithm ⋮ The condensation transition in random hypergraph 2-coloring ⋮ The number of solutions for random regular NAE-SAT ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ When does the giant component bring unsatisfiability? ⋮ Coloring complete bipartite graphs from random lists ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Selecting Complementary Pairs of Literals ⋮ Analytic description of the phase transition of inhomogeneous multigraphs ⋮ On the chromatic number of a random hypergraph ⋮ Walksat Stalls Well Below Satisfiability
This page was built for publication: Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
