Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
复制标题
超越 Talagrand 函数：测试单调性和唯一性的新下界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Jinyu Xie
中科院分区：
文献类型：
--
作者：
Xi Chen;Erik Waingarten;Jinyu Xie
对于任何双面和自适应算法的查询复杂性，我们证明了ω（n1/3）的下限，该算法测试了未知的布尔函数f：{0,1} n→{0,1}是否是单调的。单调。这改善了Belovs和Blais的同一问题的最近的下限（N1/4）（Stoc'16）。塔拉格兰的随机DNF。 。
We prove a lower bound of Ω(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω(n1/4) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs. Beyond monotonicity we prove a lower bound of Ω(√n) for two-sided, adaptive algorithms and a lower bound of Ω(n) for one-sided, non-adaptive algorithms for testing unateness, a natural generalization of monotonicity. The latter matches the linear upper bounds by Khot and Shinkar (RANDOM'16) and by Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri (2017).
实值函数的最佳不一致性测试器：适应性有帮助
影响因子：
1
作者：
Baleshzar, Roksana;Chakrabarty, Deeparnab;Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Seshadhri, C.
通讯作者：
Seshadhri, C.