A Composition Theorem via Conflict Complexity
share
Let (·) stand for the bounded-error randomized query complexity. We show that for any relation f ⊆{0,1}^n ×S and partial Boolean function g ⊆{0,1}^n ×{0,1}, _1/3(f ∘ g^n) = Ω(_4/9(f) ·√(_1/3(g))). Independently of us, Gavinsky, Lee and Santha newcomp proved this result. By an example demonstrated in their work, this bound is optimal. We prove our result by introducing a novel complexity measure called the conflict complexity of a partial Boolean function g, denoted by χ(g), which may be of independent interest. We show that χ(g) = Ω(√((g))) and (f ∘ g^n) = Ω((f) ·χ(g)).
READ FULL TEXT