Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
From MaRDI portal
Publication:3446816
DOI10.1137/S0097539703434231zbMath1120.68096arXivcond-mat/0310227MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68R10: Graph theory (including graph drawing) in computer science
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Phase transitions in theq-coloring of random hypergraphs, On Random Betweenness Constraints, Charting the replica symmetric phase, Unnamed Item, The replica symmetric phase of random constraint satisfaction problems, Biased landscapes for random constraint satisfaction problems, A topological dynamical system with two different positive sofic entropies, Walksat Stalls Well Below Satisfiability, On panchromatic colourings of a random hypergraph, Two-Colorings of a Random Hypergraph, Random 2-XORSAT at the Satisfiability Threshold, The probabilistic analysis of a greedy satisfiability algorithm, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Satisfiability threshold for power law random 2-SAT in configuration model, Satisfiability threshold for random regular \textsc{nae-sat}, The condensation transition in random hypergraph 2-coloring, 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, On the thresholds in linear and nonlinear Boolean equations, Random 2 XORSAT phase transition, Generalised and quotient models for random and/or~trees and application to satisfiability, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The asymptotic \(k\)-SAT threshold, Why almost all \(k\)-colorable graphs are easy to color, When does the giant component bring unsatisfiability?, Phase transitions in discrete structures, The list chromatic number of graphs with small clique number, Information-theoretic thresholds from the cavity method, Panchromatic 3-coloring of a random hypergraph, Charting the replica symmetric phase, Panchromatic colorings of random hypergraphs, The satisfiability threshold for random linear equations, Spin systems on Bethe lattices, The number of solutions for random regular NAE-SAT, Belief propagation on the random \(k\)-SAT model, Completeness, approximability and exponential time results for counting problems with easy decision version, Optimal testing for planted satisfiability problems, Analytic description of the phase transition of inhomogeneous multigraphs, On the chromatic number of a random hypergraph, Waiter-client and client-waiter colourability and \(k\)-SAT games, 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, Panchromatic 3-colorings of random hypergraphs, A concentration inequality for the facility location problem, Satisfiability Thresholds beyond k −XORSAT, Harnessing the Bethe free energy, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, The Decimation Process in Random k-SAT, Independent Sets in Random Graphs from the Weighted Second Moment Method, The Number of Satisfying Assignments of Random Regulark-SAT Formulas, Random k -SAT and the power of two choices, The large deviations of the whitening process in random constraint satisfaction problems, Coloring complete bipartite graphs from random lists, Selecting Complementary Pairs of Literals, Random Instances of Problems in NP – Algorithms and Statistical Physics
