The power of choice for random satisfiability

Varsha Dani; Josep Diaz; Thomas Hayes; Cristopher Moore

doi:10.1007/978-3-642-40328-6_34

The power of choice for random satisfiability

Varsha Dani
, Josep Diaz
, Thomas Hayes
, Cristopher Moore

Department of Computer Science and Engineering

University of New Mexico
Polytechnic University of Catalonia
Santa Fe Institute

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

We consider Achlioptas processes for k-SAT formulas. That is, we consider semi-random formulas with n variables and m = αn clauses, where each clause is a choice, made on-line, between two or more independent and uniformly random clauses. Our goal is to move the sat/unsat transition, making the density α = m/n at which these formulas become unsatisfiable larger or smaller than the satisfiability threshold α_k for uniformly random k-SAT formulas. We show that three choices suffice to raise the threshold for any k ≥ 3, and that two choices suffice for 3 ≤ k ≤ 50. We also show that (assuming the threshold conjecture is true) two choices suffice to lower the threshold for all k ≥ 3, and that (unconditionally) a constant number of choices suffice.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings
Pages	484-496
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-40328-6_34
State	Published - 2013
Event	16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013 - Berkeley, CA, United States Duration: Aug 21 2013 → Aug 23 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8096 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013
Country/Territory	United States
City	Berkeley, CA
Period	08/21/13 → 08/23/13

Access to Document

10.1007/978-3-642-40328-6_34

Cite this

Dani, V., Diaz, J., Hayes, T., & Moore, C. (2013). The power of choice for random satisfiability. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings (pp. 484-496). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS). https://doi.org/10.1007/978-3-642-40328-6_34

Dani, Varsha ; Diaz, Josep ; Hayes, Thomas et al. / The power of choice for random satisfiability. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. pp. 484-496 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fdbb98a9d6df4c7f98e6c0842eba4439,

title = "The power of choice for random satisfiability",

abstract = "We consider Achlioptas processes for k-SAT formulas. That is, we consider semi-random formulas with n variables and m = αn clauses, where each clause is a choice, made on-line, between two or more independent and uniformly random clauses. Our goal is to move the sat/unsat transition, making the density α = m/n at which these formulas become unsatisfiable larger or smaller than the satisfiability threshold αk for uniformly random k-SAT formulas. We show that three choices suffice to raise the threshold for any k ≥ 3, and that two choices suffice for 3 ≤ k ≤ 50. We also show that (assuming the threshold conjecture is true) two choices suffice to lower the threshold for all k ≥ 3, and that (unconditionally) a constant number of choices suffice.",

author = "Varsha Dani and Josep Diaz and Thomas Hayes and Cristopher Moore",

year = "2013",

doi = "10.1007/978-3-642-40328-6\_34",

language = "English",

isbn = "9783642403279",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "484--496",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013 ; Conference date: 21-08-2013 Through 23-08-2013",

}

Dani, V, Diaz, J, Hayes, T & Moore, C 2013, The power of choice for random satisfiability. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8096 LNCS, pp. 484-496, 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013, Berkeley, CA, United States, 08/21/13. https://doi.org/10.1007/978-3-642-40328-6_34

The power of choice for random satisfiability. / Dani, Varsha; Diaz, Josep; Hayes, Thomas et al.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. p. 484-496 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The power of choice for random satisfiability

AU - Dani, Varsha

AU - Diaz, Josep

AU - Hayes, Thomas

AU - Moore, Cristopher

PY - 2013

Y1 - 2013

N2 - We consider Achlioptas processes for k-SAT formulas. That is, we consider semi-random formulas with n variables and m = αn clauses, where each clause is a choice, made on-line, between two or more independent and uniformly random clauses. Our goal is to move the sat/unsat transition, making the density α = m/n at which these formulas become unsatisfiable larger or smaller than the satisfiability threshold αk for uniformly random k-SAT formulas. We show that three choices suffice to raise the threshold for any k ≥ 3, and that two choices suffice for 3 ≤ k ≤ 50. We also show that (assuming the threshold conjecture is true) two choices suffice to lower the threshold for all k ≥ 3, and that (unconditionally) a constant number of choices suffice.

AB - We consider Achlioptas processes for k-SAT formulas. That is, we consider semi-random formulas with n variables and m = αn clauses, where each clause is a choice, made on-line, between two or more independent and uniformly random clauses. Our goal is to move the sat/unsat transition, making the density α = m/n at which these formulas become unsatisfiable larger or smaller than the satisfiability threshold αk for uniformly random k-SAT formulas. We show that three choices suffice to raise the threshold for any k ≥ 3, and that two choices suffice for 3 ≤ k ≤ 50. We also show that (assuming the threshold conjecture is true) two choices suffice to lower the threshold for all k ≥ 3, and that (unconditionally) a constant number of choices suffice.

UR - https://www.scopus.com/pages/publications/84885203942

U2 - 10.1007/978-3-642-40328-6_34

DO - 10.1007/978-3-642-40328-6_34

M3 - Conference contribution

AN - SCOPUS:84885203942

SN - 9783642403279

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 484

EP - 496

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013

Y2 - 21 August 2013 through 23 August 2013

ER -

Dani V, Diaz J, Hayes T, Moore C. The power of choice for random satisfiability. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. p. 484-496. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40328-6_34

The power of choice for random satisfiability

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this