Name
Abstract | ||
|---|---|---|
We consider Achlioptas processes for k-SAT formulas. We create a semi-random formula with n variables and m clauses, where each clause is a choice, made on-line, between two or more uniformly random clauses. Our goal is to delay the satisfiability/unsatisfiability transition, keeping the formula satisfiable up to densities m/n beyond the satisfiability threshold alpha_k for random k-SAT. We show that three choices suffice to raise the threshold for any k >= 3, and that two choices suffice for all 3 <= k <= 25. We also show that two choices suffice to lower the threshold for all k >= 3, making the formula unsatisfiable at a density below alpha_k. |
Year | Venue | DocType |
|---|---|---|
2013 | APPROX-RANDOM | Conference |
Volume | Citations | PageRank |
abs/1211.6997 | 1 | 0.35 |
References | Authors | |
20 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Varsha Dani | 1 | 432 | 40.05 |
| Josep Diaz | 2 | 1 | 0.35 |
| Thomas P. Hayes | 3 | 659 | 54.21 |
| Cristopher Moore | 4 | 1765 | 160.55 |