The asymptotic \(k\)-SAT threshold
From MaRDI portal
Publication:900872
DOI10.1016/j.aim.2015.11.007zbMath1394.60007arXiv1310.2728OpenAlexW2105860081MaRDI QIDQ900872
Amin Coja-Oghlan, Konstantinos D. Panagiotou
Publication date: 23 December 2015
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1310.2728
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Critical phenomena in equilibrium statistical mechanics (82B27)
Related Items (32)
Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ Phase transitions in discrete structures ⋮ The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ Information-theoretic thresholds from the cavity method ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Maximum independent sets on random regular graphs ⋮ Statistical limits of spiked tensor models ⋮ Counting Solutions to Random CNF Formulas ⋮ Free energy subadditivity for symmetric random Hamiltonians ⋮ Lower bounds on the chromatic number of random graphs ⋮ Harnessing the Bethe free energy ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ What is the satisfiability threshold of random balanced Boolean expressions? ⋮ Combinatorial statistics and the sciences ⋮ Ultrametricity in spin glasses ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ Bethe states of random factor graphs ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ The satisfiability threshold for random linear equations ⋮ Spin systems on Bethe lattices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The number of solutions for random regular NAE-SAT ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Streamlining variational inference for constraint satisfaction problems ⋮ Walksat Stalls Well Below Satisfiability ⋮ A model of random industrial SAT
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Upper-bounding the \(k\)-colorability threshold by counting covers
- On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
- The 3-XORSAT threshold.
- An elementary proof of the local central limit theorem
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Proof of the Satisfiability Conjecture for Large k
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Survey propagation as local equilibrium equations
- A Remark on Stirling's Formula
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- A new look at survey propagation and its generalizations
- Information, Physics, and Computation
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- Entropy of theK-Satisfiability Problem
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Bounds on Threshold of Regular Random k-SAT
- A threshold for unsatisfiability
- Random Formulas Have Frozen Variables
- The asymptotic k-SAT threshold
- Satisfiability threshold for random regular NAE-SAT
- Survey propagation: An algorithm for satisfiability
- The Satisfiability Threshold fork-XORSAT
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A Better Algorithm for Random k-SAT
- Catching the k-NAESAT threshold
- The freezing threshold for k-colourings of a random graph
- Threshold values of random K‐SAT from the cavity method
- Poisson Cloning Model for Random Graphs
- Going after the k-SAT threshold
- The condensation transition in random hypergraph 2-coloring
This page was built for publication: The asymptotic \(k\)-SAT threshold
