Random k -SAT and the power of two choices
From MaRDI portal
Publication:3192377
DOI10.1002/rsa.20534zbMath1322.05125arXiv1209.5313MaRDI QIDQ3192377
Publication date: 12 October 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.5313
05C80: Random graphs (graph-theoretic aspects)
60C05: Combinatorial probability
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
On the Power of Choice for Boolean Functions, Waiter-client and client-waiter colourability and \(k\)-SAT games
Cites Work
- Achlioptas process phase transitions are continuous
- Small subgraphs in random graphs and the power of multiple choices
- Regular random \(k\)-SAT: Properties of balanced formulas
- Birth control for giants
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- The scaling window of the 2-SAT transition
- Avoiding a giant component
- The Bohman-Frieze process near criticality
- Delaying satisfiability for random 2SAT
- Hamiltonicity thresholds in Achlioptas processes
- Selecting Complementary Pairs of Literals
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- On the Random Satisfiable Process
- Avoiding small subgraphs in Achlioptas processes
- The Evolution of Random Graphs
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Aggregation models with limited choice and the multiplicative coalescent
- Creating a Giant Component
- Automata, Languages and Programming
- Embracing the giant component
- Lower bounds for random 3-SAT via differential equations
