A composition theorem for randomized query complexity via max conflict complexity
- Publication Type:
- Conference Proceeding
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Let $R_\epsilon(\cdot)$ stand for the bounded-error randomized query
complexity with error $\epsilon > 0$. For any relation $f \subseteq \{0,1\}^n
\times S$ and partial Boolean function $g \subseteq \{0,1\}^m \times \{0,1\}$,
we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot
\sqrt{R_{1/3}(g)})$, where $f \circ g^n \subseteq (\{0,1\}^m)^n \times S$ is
the composition of $f$ and $g$. We give an example of a relation $f$ and
partial Boolean function $g$ for which this lower bound is tight.
We prove our composition theorem by introducing a new complexity measure, the
max conflict complexity $\bar \chi(g)$ of a partial Boolean function $g$. We
show $\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})$ for any (partial) function
$g$ and $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))$; these
two bounds imply our composition result. We further show that $\bar \chi(g)$ is
always at least as large as the sabotage complexity of $g$, introduced by
Ben-David and Kothari.
Please use this identifier to cite or link to this item: