Biased random k‐SAT
From MaRDI portal
Publication:6074657
DOI10.1002/rsa.20996zbMath1522.68377arXiv1906.05127MaRDI QIDQ6074657
Publication date: 12 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.05127
Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on random \(k\)-SAT for moderately growing \(k\)
- Spines of random constraint satisfaction problems: definition and connection with computational complexity
- Differential equations for random processes and random graphs
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Random 2-SAT with prescribed literal degrees
- Critical behavior in the computational cost of satisfiability testing
- The scaling window of the 2-SAT transition
- Proof of the Satisfiability Conjecture for Large k
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Many hard examples for resolution
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- On the critical percolation probabilities
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Entropy of theK-Satisfiability Problem
- Balls and bins: A study in negative dependence
- Speed and concentration of the covering time for structured coupon collectors
- The asymptotic k-SAT threshold
- Theory and Applications of Satisfiability Testing
- The high temperature case for the random \(K\)-sat problem
- Lower bounds for random 3-SAT via differential equations
This page was built for publication: Biased random k‐SAT