A composition theorem for randomized query complexity via max conflict complexity
A composition theorem for randomized query complexity via max conflict complexity
复制标题
通过最大冲突复杂性实现随机查询复杂性的组合定理
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Swagato Sanyal
中科院分区：
文献类型：
--
作者：
Dmitry Gavinsky;Troy Lee;M. Santha;Swagato Sanyal
Let $R_epsilon(cdot)$ stand for the bounded-error randomized query complexity with error $epsilon>0$. For any relation $f subseteq {0,1}^n imes S$ and partial Boolean function $g subseteq {0,1}^m imes {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 imes 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 $ar chi(g)$ of a partial Boolean function $g$. We show $ar 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 ar chi(g))$; these two bounds imply our composition result. We further show that $ar chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.
Let $R_epsilon(cdot)$ stand for the bounded-error randomized query complexity with error $epsilon>0$. For any relation $f subseteq {0,1}^n imes S$ and partial Boolean function $g subseteq {0,1}^m imes {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 imes 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 $ar chi(g)$ of a partial Boolean function $g$. We show $ar 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 ar chi(g))$; these two bounds imply our composition result. We further show that $ar chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.