随机查询组合与破坏复杂性

《ACM Transactions on Computation Theory》：Randomized query composition and sabotage complexity

本研究证明破坏复杂性RS(f°g^n)至少为最大分布式查询复杂性的乘积，引入R^p度量并验证了完全二进制NAND树函数中RS与分布式复杂性的多项式分离。

　　

摘要

设 $R_{?}$ 表示错误概率为 ? 时的随机查询复杂度，而 $R:=R_{1/3}$ 表示另一种随机查询复杂度。在本研究中，我们探讨了一个完美的组合定理是否成立：对于关系 和一个总内部函数 g：{0, 1}^m → {0, 1}。Ben-David 和 Kothari（ICALP 2016, TOC 2018）证明了对于关系 和总内部函数 g，完美组合定理是否成立。他们还证明了当 f 是任意关系且 g 是任意偏函数时，破坏复杂度