scientific article; zbMATH DE number 7205015
From MaRDI portal
Publication:5111724
DOI10.4230/LIPIcs.ESA.2017.37zbMath1442.68156arXiv1706.08431MaRDI QIDQ5111724
Andrew M. Sutton, Tobias Friedrich, Anton Krohmer, Thomas Sauerwald, Ralf Rothenberger
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1706.08431
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)
Related Items (6)
The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ Popularity-similarity random SAT formulas ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving non-uniform planted and filtered random SAT formulas greedily
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A threshold for unsatisfiability
- Regular random \(k\)-SAT: Properties of balanced formulas
- The asymptotic \(k\)-SAT threshold
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Geometric inhomogeneous random graphs
- On the satisfiability threshold of formulas with three literals per clause
- A Random Graph Model for Power Law Graphs
- Lock-Free Algorithms under Stochastic Schedulers
- Random Graphs and Complex Networks
- Proof of the Satisfiability Conjecture for Large k
- On Sharp Thresholds in Random Geometric Graphs
- Emergence of Scaling in Random Networks
- The Fractal Dimension of SAT Formulas
- Power-Law Distributions in Empirical Data
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- On a Correlation Inequality of Farr
- The Structure and Function of Complex Networks
- The probabilistic analysis of a greedy satisfiability algorithm
- On the solution‐space geometry of random constraint satisfaction problems
- Concentration of Measure for the Analysis of Randomized Algorithms
- Random 2-SAT: Results and problems
This page was built for publication:
