@inproceedings{2c41b65c17194e4696e001d77f86543c,

title = "Bounds on the satisfiability threshold for power law distributed random SAT",

abstract = "Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The averagecase analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random k-SAT on n variables, m = ϵ(n) clauses, and a power law distribution on the variable occurrences with exponent β. We observe a satisfiability threshold at β≤(2k-1)/(k-1). This threshold is tight in the sense that instances with β ≥ (2k-1)/(k-1)-ϵ for any constant ϵ > 0 are unsatisfiable with high probability (w. h. p.). For β > (2k-1)/(k-1)+ ϵ, the picture is reminiscent of the uniform case: instances are satisfiable w. h. p. for sufficiently small constant clause-variable ratios m/n; they are unsatisfiable above a ratio m/n that depends on β.",

keywords = "Phase transitions, Power law distribution, Random SAT, Random structures, Satisfiability, Scale-freeness",

author = "Tobias Friedrich and Anton Krohmer and Ralf Rothenberger and Thomas Sauerwald and Sutton, {Andrew M.}",

year = "2017",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2017.37",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Christian Sohler and Christian Sohler and Kirk Pruhs",

booktitle = "25th European Symposium on Algorithms, ESA 2017",

note = "25th European Symposium on Algorithms, ESA 2017 ; Conference date: 04-09-2017 Through 06-09-2017",

}