Satisfiability threshold for power law random 2-SAT in configuration model
From MaRDI portal
Publication:5896832
DOI10.1016/j.tcs.2021.07.028OpenAlexW3191322193MaRDI QIDQ5896832
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
Related Items
Power-law Lévy processes, power-law vector random fields, and some extensions, The impact of heterogeneity and geometry on the proof complexity of random satisfiability
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generating SAT instances with community structure
- A threshold for unsatisfiability
- Regular random \(k\)-SAT: Properties of balanced formulas
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
- The diameter of a scale-free random graph
- On the satisfiability threshold of formulas with three literals per clause
- Random 2-SAT with prescribed literal degrees
- Generating hard satisfiability problems
- The degree sequence of a scale-free random graph process
- A Random Graph Model for Power Law Graphs
- Proof of the Satisfiability Conjecture for Large k
- Emergence of Scaling in Random Networks
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Power-Law Distributions in Empirical Data
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Computing and Combinatorics
- Survey propagation: An algorithm for satisfiability
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A Better Algorithm for Random k-SAT
- The probabilistic analysis of a greedy satisfiability algorithm
- Going after the k-SAT threshold
- Random 2-SAT: Results and problems
- Lower bounds for random 3-SAT via differential equations
