Bounds on the satisfiability threshold for power law distributed random SAT

DOI10.4230/LIPICS.ESA.2017.37zbMATH Open1442.68156arXiv1706.08431MaRDI QIDQ5111724FDOQ5111724

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

Publication date: 27 May 2020

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

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

zbMATH Keywords

phase transitionssatisfiabilityrandom structuresrandom SATpower law distributionscale-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)

Cites Work

• Power-law distributions in empirical data
• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• The Structure and Function of Complex Networks
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Concentration of Measure for the Analysis of Randomized Algorithms
• Approximating the unsatisfiability threshold of random formulas
• A Random Graph Model for Power Law Graphs
• The Fractal Dimension of SAT Formulas
• Proof of the Satisfiability Conjecture for Large k
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the solution‐space geometry of random constraint satisfaction problems
• On the satisfiability threshold of formulas with three literals per clause
• Title not available (Why is that?)
• The probabilistic analysis of a greedy satisfiability algorithm
• Random 2-SAT: Results and problems
• A threshold for unsatisfiability
• On a Correlation Inequality of Farr
• Regular random \(k\)-SAT: Properties of balanced formulas
• The asymptotic \(k\)-SAT threshold
• Geometric inhomogeneous random graphs
• Lock-free algorithms under stochastic schedulers
• On Sharp Thresholds in Random Geometric Graphs
• Title not available (Why is that?)

Cited In (7)

• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Solving non-uniform planted and filtered random SAT formulas greedily
• Popularity-similarity random SAT formulas
• Title not available (Why is that?)
• Satisfiability threshold for power law random 2-SAT in configuration model
• Satisfiability threshold for power law random 2-SAT in configuration model
• Title not available (Why is that?)

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)