Satisfiability threshold for power law random 2-SAT in configuration model

DOI10.1016/J.TCS.2021.07.028MaRDI QIDQ5896832zbMATH OpenOpenAlexFDO

Authors Oleksii Omelchenko, Andrei A. Bulatov

Publication date 27 September 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionpower lawsatisfiability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Satisfiability threshold for power law random 2-SAT in configuration model
• Bounds on the satisfiability threshold for power law distributed random SAT
• Random 2-SAT: Results and problems
• Rigorous results for random (2+p)-SAT
• RANDOM 2‐SAT Does Not Depend on a Giant

Cites work

• A better algorithm for random \(k\)-SAT
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A Random Graph Model for Power Law Graphs
• A threshold for unsatisfiability
• Approximating the unsatisfiability threshold of random formulas
• Bounds on the satisfiability threshold for power law distributed random SAT
• Computing and Combinatorics
• Emergence of Scaling in Random Networks
• Generating hard satisfiability problems
• Generating SAT instances with community structure
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Going after the k-SAT threshold
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1113991 (Why is no real title available?)
• Lower bounds for random 3-SAT via differential equations
• On the satisfiability threshold of formulas with three literals per clause
• Power-law distributions in empirical data
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Proof of the satisfiability conjecture for large k
• Random 2-SAT with prescribed literal degrees
• Random 2-SAT: Results and problems
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Regular random \(k\)-SAT: Properties of balanced formulas
• Sharp thresholds of graph properties, and the k-sat problem
• Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
• Survey propagation: An algorithm for satisfiability
• The degree sequence of a scale-free random graph process
• The diameter of a scale-free random graph
• The probabilistic analysis of a greedy satisfiability algorithm

Cited in

(6)

• Power-law Lévy processes, power-law vector random fields, and some extensions
• The satisfiability threshold for non-uniform random 2-SAT
• Bounds on the satisfiability threshold for power law distributed random SAT
• Satisfiability threshold for power law random 2-SAT in configuration model
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses

Describes a project that uses

Uses Software

• plfit

This page was built for publication: Satisfiability threshold for power law random 2-SAT in configuration model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896832)