Delaying satisfiability for random 2SAT
From MaRDI portal
Publication:2852549
DOI10.1002/rsa.20465zbMath1272.05185OpenAlexW2096307009MaRDI QIDQ2852549
Dan Vilenchik, Alistair Sinclair
Publication date: 9 October 2013
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20465
Related Items
Waiter-client and client-waiter colourability and \(k\)-SAT games, Random k -SAT and the power of two choices, On the Power of Choice for Boolean Functions
Cites Work
- A threshold for unsatisfiability
- Birth control for giants
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Avoiding a giant component
- Hamiltonicity thresholds in Achlioptas processes
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- RANDOM 2‐SAT Does Not Depend on a Giant
- Avoiding small subgraphs in Achlioptas processes
- Sharp thresholds of graph properties, and the $k$-sat problem
- Balanced Allocations
- Creating a Giant Component
- A phase transition for avoiding a giant component
- Embracing the giant component