## Authors: Tobias Friedrich and Ralf Rothenberger

## Paper Information

Title: | Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT |

Authors: | Tobias Friedrich and Ralf Rothenberger |

Proceedings: | SAT Proceedings |

Editors: | Christoph M. Wintersteiger and Olaf Beyersdorff |

Keywords: | satisfiability threshold, sharpness, random SAT, power-law |

Abstract: | ABSTRACT. We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number t = t(n) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble (p_n)_{n\in\N} of arbitrary probability distributions on the variable occurrences is sharp if ||p||_2 = O_n(t^(-2/k)) and ||p||_infinity = o_n(t^(-k/(2k-1)) * log^(-(k-1)/(2k-1))(t)). This result generalizes Friedgutâ€™s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution. |

Pages: | 19 |

Talk: | Jul 11 09:00 (Session 60F: Theory) |

Paper: |