Satisfiability threshold for power law random 2-SAT in configuration model
From MaRDI portal
Publication:5896832
DOI10.1016/J.TCS.2021.07.028OpenAlexW3191322193MaRDI QIDQ5896832FDOQ5896832
Authors: 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
Recommendations
Cites Work
- Power-law distributions in empirical data
- Emergence of Scaling in Random Networks
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- The degree sequence of a scale-free random graph process
- The diameter of a scale-free random graph
- Approximating the unsatisfiability threshold of random formulas
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A Random Graph Model for Power Law Graphs
- Generating SAT instances with community structure
- Proof of the satisfiability conjecture for large \(k\)
- Sharp thresholds of graph properties, and the $k$-sat problem
- On the satisfiability threshold of formulas with three literals per clause
- Title not available (Why is that?)
- Title not available (Why is that?)
- Survey propagation: An algorithm for satisfiability
- The probabilistic analysis of a greedy satisfiability algorithm
- Random 2-SAT: Results and problems
- Lower bounds for random 3-SAT via differential equations
- A threshold for unsatisfiability
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Going after the \(k\)-SAT threshold
- A better algorithm for random \(k\)-SAT
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Generating hard satisfiability problems
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Regular random \(k\)-SAT: Properties of balanced formulas
- Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
- Bounds on the satisfiability threshold for power law distributed random SAT
- Random 2-SAT with prescribed literal degrees
- Computing and Combinatorics
Cited In (4)
- Bounds on the satisfiability threshold for power law distributed random SAT
- The impact of heterogeneity and geometry on the proof complexity of random satisfiability
- Power-law Lévy processes, power-law vector random fields, and some extensions
- Satisfiability threshold for power law random 2-SAT in configuration model
Uses Software
This page was built for publication: Satisfiability threshold for power law random 2-SAT in configuration model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896832)
