Bounds on the satisfiability threshold for power law distributed random SAT

DOI10.4230/LIPICS.ESA.2017.37MaRDI QIDQ5111724zbMATH OpenFDO

Authors Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, Andrew M. Sutton

Publication date 27 May 2020

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

zbMATH Keywords

phase transitionspower law distributionrandom SATrandom structuressatisfiabilityscale-freeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Recommendations

• Satisfiability threshold for power law random 2-SAT in configuration model
• Satisfiability threshold for power law random 2-SAT in configuration model
• Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Theory and Applications of Satisfiability Testing

Cites work

• 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
• Concentration of Measure for the Analysis of Randomized Algorithms
• Emergence of Scaling in Random Networks
• Geometric inhomogeneous random graphs
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• Lock-free algorithms under stochastic schedulers
• On a Correlation Inequality of Farr
• On sharp thresholds in random geometric graphs
• On the satisfiability threshold of formulas with three literals per clause
• On the solution-space geometry of random constraint satisfaction problems
• Power-law distributions in empirical data
• Proof of the satisfiability conjecture for large k
• Random 2-SAT: Results and problems
• Random graphs and complex networks. Volume 1
• Regular random \(k\)-SAT: Properties of balanced formulas
• Sharp thresholds of graph properties, and the k-sat problem
• The asymptotic k-SAT threshold
• The fractal dimension of SAT formulas
• The probabilistic analysis of a greedy satisfiability algorithm
• The Structure and Function of Complex Networks

Cited in

(8)

• Solving non-uniform planted and filtered random SAT formulas greedily
• Popularity-similarity random SAT formulas
• 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
• 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: Bounds on the satisfiability threshold for power law distributed random SAT

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