A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d
复制标题
A o(d) · polylog n 超网格上布尔函数的单调性测试器 [n]d
DOI：
10.1137/1.9781611975031.139
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
C. Seshadhri
中科院分区：
文献类型：
--
作者：
Hadley Black;Deeparnab Chakrabarty;C. Seshadhri
我们研究了在高网格[n] d上的布尔函数的单调性测试，并设计了一个非自适应测试仪，其查询复杂性为O（D5/6）·Poly（log n，1/e）工作，最著名的测试者在D中具有线性的查询复杂性，但我们与N = 2DO相关。边缘到超级格里德。我们的主要技术贡献是增强超级格里德的玛格利斯风格的等值效果，我们的测试仪像以前的HyperCube域测试人员一样，在此结构上进行了定向的随机步行。
We study monotonicity testing of Boolean functions over the hypergrid [n]d and design a non-adaptive tester with 1-sided error whose query complexity is O(d5/6) · poly(log n, 1/e). Previous to our work, the best known testers had query complexity linear in d but independent of n. We improve upon these testers as long as n = 2do(1). To obtain our results, we work with what we call the augmented hypergrid, which adds extra edges to the hypergrid. Our main technical contribution is a Margulis-style isoperimetric result for the augmented hypergrid, and our tester, like previous testers for the hypercube domain, performs directed random walks on this structure.