Name
Abstract | ||
|---|---|---|
Let f : {0, 1}n → {0, 1}. Let μ be a product probability measure on {0, 1}n. For ε ≥ 0, we define Dε(f), the ε-approximate decision tree complexity of f, to be the minimum depth of a decision tree T with μ(T(x) ≠ f(x)) ≤ ε. For j = 0 or 1 and for δ ≥ 0, we define Cj,δ(f), the δ-approximate j-certificate complexity of f, to be the minimum certificate complexity of a set A ⊆ Ω with μ(AΔf−1(j)) ≤ ε. Note that if μ(x) 0 for all x then D0(f) = D(f) and Cj,0(f) = Cj(f) are the ordinary decision tree and j-certificate complexities of f, respectively. We extend the well-known result, D(f) ≤ C1(f)C0(f) [Blum and Impagliazzo 1987; Hartmanis and Hemachandra 1991; Tardos 1989], proving that for all ε 0 there exists a δ 0 and a constant K = K(ε, δ) 0 such that for all n, μ, f, Dε(f) ≤ K C1,δ(f)C0,δ (f). We also give a partial answer to a related question on query complexity raised by Tardos [1989]. We prove generalizations of these results to general product probability spaces. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2003685.2003688 | TOCT |
Keywords | Field | DocType |
query complexity,minimum certificate complexity,general product probability space,ordinary decision tree,decision tree,constant k,k c1,approximate query complexity,approximate j-certificate complexity,j-certificate complexity,approximate decision tree complexity,communication complexity,probability measure | Discrete mathematics,Combinatorics,Generalization,Probability measure,Communication complexity,Mathematics | Journal |
Volume | Issue | Citations |
3 | 1 | 0 |
PageRank | References | Authors |
0.34 | 7 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Clifford Smyth | 1 | 24 | 6.91 |