A Composition Theorem via Conflict Complexity

Abstract

Let $\mathbb{R}(\cdot )$ stand for the bounded-error randomized query complexity. We show that for any relation $f\subseteq \{0,1{\}}^n\times \mathcal{S}$ and partial Boolean function $g\subseteq \{0,1{\}}^n\times \{0,1\}$, ${\mathbb{R}}_{1/3}(f\circ g^n)=\Omega ({\mathbb{R}}_{4/9}(f)\cdot \sqrt{{\mathbb{R}}_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha \cite{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 \emph{conflict complexity} of a partial Boolean function $g$, denoted by $\chi (g)$, which may be of independent interest. We show that $\chi (g)=\Omega (\sqrt{\mathbb{R}(g)})$ and $\mathbb{R}(f\circ g^n)=\Omega (\mathbb{R}(f)\cdot \chi (g))$.