Name
Abstract | ||
|---|---|---|
Let be a set of terms over an arbitrary (but finite) number of Boolean variables. Let U() be the set of truth assignments that satisfy exactly one term in . Motivated by questions in computational complexity, Rudich conjectured that there exist ∊, δ 0 such that, if is any set of terms for which U() contains at least a (1−∊)-fraction of all truth assignments, then there exists a term t ∈ such that at least a δ-fraction of assignments satisfy some term of sharing a variable with t [8]. We prove a stronger version: for any independent assignment of the variables (not necessarily the uniform one), if the measure of U() is at least 1 − ∊, there exists a t ∈ such that the measure of the set of assignments satisfying either t or some term incompatible with t (i.e., having no satisfying assignments in common with t) is at least $\Gd = 1-\Ge-\frac{4\Ge}{1-\Ge}$. (A key part of the proof is a correlation-like inequality on events in a finite product probability space that is in some sense dual to Reimer's inequality [11], a.k.a. the BKR inequality [5], or the van den Berg–Kesten conjecture [3].) |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1017/S0963548310000465 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
boolean variable,finite product probability space,correlation-like inequality,independent assignment,satisfying assignment,kesten conjecture,truth assignment,bkr inequality,dual bkr inequality,key part,computational complexity | Discrete mathematics,Combinatorics,Probability space,Existential quantification,Inequality,Boolean data type,Conjecture,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
20 | 2 | 0963-5483 |
Citations | PageRank | References |
3 | 0.37 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeff Kahn | 1 | 11 | 1.81 |
| Michael Saks | 2 | 2595 | 302.11 |
| Clifford Smyth | 3 | 24 | 6.91 |