Proof of the Satisfiability Conjecture for Large k

DOI10.1145/2746539.2746619zbMath1321.68304arXiv1411.0650OpenAlexW2070702809MaRDI QIDQ2941489

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.0650

zbMATH Keywords

condensation constraint satisfaction problem belief propagation replica symmetry breaking random \(k\)-SAT survey propagation satisfiability threshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

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, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Storage capacity in symmetric binary perceptrons, The Number of Satisfying Assignments of Random Regulark-SAT Formulas, Random subcube intersection graphs. I: Cliques and covering, Belief propagation for the maximum-weight independent set and minimum spanning tree problems, Information-theoretic thresholds from the cavity method, The asymptotics of the clustering transition for random constraint satisfaction problems, Counting Solutions to Random CNF Formulas, Lower bounds on the chromatic number of random graphs, Harnessing the Bethe free energy, The number of satisfying assignments of random 2‐SAT formulas, Biased random k‐SAT, Combinatorial statistics and the sciences, Ultrametricity in spin glasses, One-step replica symmetry breaking of random regular NAE-SAT. II, Local minima in disordered mean-field ferromagnets, The asymptotic \(k\)-SAT threshold, CHAMP: a multipass algorithm for Max Sat based on saver variables, Critical window of the symmetric perceptron, Sharp thresholds in adaptive random graph processes, Go-MOCE: greedy order method of conditional expectations for Max Sat, Zero-temperature dynamics in the dilute Curie-Weiss model, Bethe states of random factor graphs, Constructing concrete hard instances of the maximum independent set problem, Satisfiability threshold for power law random 2-SAT in configuration model, Charting the replica symmetric phase, Charting the replica symmetric phase, Constraining the clustering transition for colorings of sparse random graphs, The satisfiability threshold for random linear equations, Optimal testing for planted satisfiability problems, Spin systems on Bethe lattices, The Stripping Process Can be Slow: Part II, Unnamed Item, Unnamed Item, Unnamed Item, New models for generating hard random Boolean formulas and disjunctive logic programs, Probabilistic characterization of random Max \(r\)-Sat, Unnamed Item, The number of solutions for random regular NAE-SAT, On the spectral gap of spherical spin glass dynamics, The potential of quantum annealing for rapid solution structure identification, The replica symmetric phase of random constraint satisfaction problems, Super solutions of random \((3 + p)\)-SAT, Speed and concentration of the covering time for structured coupon collectors, Belief propagation on the random \(k\)-SAT model, Using the method of conditional expectations to supply an improved starting point for CCLS, Streamlining variational inference for constraint satisfaction problems, Biased landscapes for random constraint satisfaction problems, On Super Strong ETH, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Walksat Stalls Well Below Satisfiability, Decoding from Pooled Data: Sharp Information-Theoretic Bounds, A model of random industrial SAT

Uses Software

Graphs

Cites Work