Proof of the Satisfiability Conjecture for Large k

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

Allan Sly, Nike Sun, Jian Ding

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

condensationconstraint satisfaction problembelief propagationreplica symmetry breakingrandom \(k\)-SATsurvey propagationsatisfiability threshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (56)

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

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Proof of the Satisfiability Conjecture for Large k