标题： 相对误差单调性测试 显示英文标题

标题： Relative-error unateness testing

摘要： 布尔函数的相对误差性质测试模型已成为近期重要的研究课题 [CDH+24][CPPS25a][CPPS25b] 在本文中，我们考虑对未知且任意的$f: \{0,1\}^n \to \{0,1\}$进行相对误差测试的问题，该函数具有单增函数的性质，即 在每个$n$输入变量上，该函数要么是单调非递增，要么是单调非递减。 我们的第一个结果是针对此问题的一个单边非自适应算法，该算法进行$\tilde{O}(\log(N)/\epsilon)$个样本和查询，其中$N=|f^{-1}(1)|$是被测试函数的满足赋值的数量，$N$的值作为算法的输入参数给出。 在此算法的基础上，我们接下来给出一个针对此问题的单边自适应算法，该算法不需要给出$N$的值，并且以高概率进行$\tilde{O}(\log(N)/\epsilon)$个样本和查询。 我们还给出了自适应和非自适应双向算法的下界，这些算法给出的$N$值最多是常数倍的因子。 在非自适应情况下，我们的下界与我们提供的算法的复杂度基本匹配。 显示英文摘要

摘要： The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary $f: \{0,1\}^n \to \{0,1\}$ for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the $n$ input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes $\tilde{O}(\log(N)/\epsilon)$ samples and queries, where $N=|f^{-1}(1)|$ is the number of satisfying assignments of the function that is being tested and the value of $N$ is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of $N$ and with high probability makes $\tilde{O}(\log(N)/\epsilon)$ samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of $N$ up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.