scientific article; zbMATH DE number 7561554

DOI10.4230/LIPIcs.ICALP.2019.61MaRDI QIDQ5091218

Tobias Friedrich, Ralf Rothenberger

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

sharpnessrandom SATnon-uniform distribution2-SATsatisfiability threshold

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

The impact of heterogeneity and geometry on the proof complexity of random satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Regular random \(k\)-SAT: Properties of balanced formulas
• The asymptotic \(k\)-SAT threshold
• Which problems have strongly exponential complexity?
• Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
• On the satisfiability threshold of formulas with three literals per clause
• Random 2-SAT with prescribed literal degrees
• On the Hardness of SAT with Community Structure
• The Community Structure of SAT Formulas
• Proof of the Satisfiability Conjecture for Large k
• On Sharp Thresholds in Random Geometric Graphs
• The Number of Satisfying Assignments of Random Regulark-SAT Formulas
• The Fractal Dimension of SAT Formulas
• The condensation phase transition in the regular $k$-SAT model
• Bounds on Threshold of Regular Random k-SAT
• Reducibility among Combinatorial Problems
• The asymptotic k-SAT threshold
• The probabilistic analysis of a greedy satisfiability algorithm
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The complexity of theorem-proving procedures
• On the complexity of \(k\)-SAT
• Rigorous results for random (\(2+p)\)-SAT

This page was built for publication: