A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract
复制标题
偏函数随机查询复杂度的紧组合定理：扩展摘要
DOI：
10.1109/focs46700.2020.00031
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Eric Blais
中科院分区：
文献类型：
--
作者：
S. Ben;Eric Blais
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions <tex>$f$</tex> and <tex>$g$</tex> such that <tex>$\mathrm{R}(f\circ g)\ll \mathrm{R}(f)\mathrm{R}(g)$</tex>. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of <tex>$f$</tex>). Second, we show that for all <tex>$f$</tex> and <tex>$g,\ \mathrm{R}(f\circ g) = \Omega(\text{noisyR}(f)\ \mathrm{R}(g))$</tex>, where <tex>$\text{noisyR}(f)$</tex> is a measure describing the cost of computing <tex>$f$</tex> on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure <tex>$M(\cdot)$</tex> satisfying <tex>$\mathrm{R}(f\circ g)=\Omega(M(f)\mathrm{R}(g))$</tex> for all <tex>$f$</tex> and <tex>$g$</tex>, it must hold that <tex>$\text{noisyR}(f)=\Omega(M(f))$</tex> for all <tex>$f$</tex>. We also give a clean characterization of the measure <tex>$\text{noisyR}(f)$</tex>: it satisfies <tex>$\text{noisyR}(f)=\Theta(\mathrm{R}(f\circ\text{GapMaj}_{n})/\mathrm{R}(\text{GapMaj}_{n}))$</tex>, where <tex>$n$</tex> is the input size of <tex>$f$</tex> and <tex>$\text{GapMaj}_{n}$</tex> is the <tex>$\sqrt{n}$</tex>-gap majority function on <tex>$n$</tex> bits.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions <tex>$f$</tex> and <tex>$g$</tex> such that <tex>$\mathrm{R}(f\circ g)\ll \mathrm{R}(f)\mathrm{R}(g)$</tex>. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of <tex>$f$</tex>). Second, we show that for all <tex>$f$</tex> and <tex>$g,\ \mathrm{R}(f\circ g) = \Omega(\text{noisyR}(f)\ \mathrm{R}(g))$</tex>, where <tex>$\text{noisyR}(f)$</tex> is a measure describing the cost of computing <tex>$f$</tex> on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure <tex>$M(\cdot)$</tex> satisfying <tex>$\mathrm{R}(f\circ g)=\Omega(M(f)\mathrm{R}(g))$</tex> for all <tex>$f$</tex> and <tex>$g$</tex>, it must hold that <tex>$\text{noisyR}(f)=\Omega(M(f))$</tex> for all <tex>$f$</tex>. We also give a clean characterization of the measure <tex>$\text{noisyR}(f)$</tex>: it satisfies <tex>$\text{noisyR}(f)=\Theta(\mathrm{R}(f\circ\text{GapMaj}_{n})/\mathrm{R}(\text{GapMaj}_{n}))$</tex>, where <tex>$n$</tex> is the input size of <tex>$f$</tex> and <tex>$\text{GapMaj}_{n}$</tex> is the <tex>$\sqrt{n}$</tex>-gap majority function on <tex>$n$</tex> bits.
影响因子：
0.7
作者：
Göös, Mika;Jayram, T. S.;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas