Parameterized Property Testing of Functions
Parameterized Property Testing of Functions
复制标题
函数的参数化属性测试
DOI：
10.1145/3155296
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nithin M. Varma
中科院分区：
文献类型：
--
作者：
R. Pallavoor;Sofya Raskhodnikova;Nithin M. Varma
我们调查的参数，其中次线性时间算法的复杂性应表示。我们的目标是找到输入参数，适合正在研究的特定问题的组合和设计的算法，运行速度更快时，这些参数是小的。这个方向使我们能够超过（最坏情况下）的下限，表示在输入大小，为几个问题。我们的目标是开发一个类似的水平的理解的复杂性的次线性时间算法的一个，使研究在参数化的复杂性的经典算法。具体来说，我们专注于测试函数的属性。通过将查询复杂度参数化为输入函数图像的大小r，我们得到了f：[n]→ R形式的函数的单调性和凸性的测试器，其查询复杂度为O（log r），不依赖于n。单调性的结果绕过了Fischer（Inf. COMPUT. 2004年，针对这个问题。我们提出了其他几个参数化的测试程序，提供令人信服的证据表明，表示属性测试程序的查询复杂性的输入大小并不总是最好的选择。
We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us to surpass the (worst-case) lower bounds, expressed in terms of the input size, for several problems. Our aim is to develop a similar level of understanding of the complexity of sublinear-time algorithms to the one that was enabled by research in parameterized complexity for classical algorithms. Specifically, we focus on testing properties of functions. By parameterizing the query complexity in terms of the size r of the image of the input function, we obtain testers for monotonicity and convexity of functions of the form f:[n]→ R with query complexity O (log r), with no dependence on n. The result for monotonicity circumvents the Ω (log n) lower bound by Fischer (Inf. Comput. 2004) for this problem. We present several other parameterized testers, providing compelling evidence that expressing the query complexity of property testers in terms of the input size is not always the best choice.
实值函数的最佳不一致性测试器：适应性有帮助
影响因子：
1
作者：
Baleshzar, Roksana;Chakrabarty, Deeparnab;Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Seshadhri, C.
通讯作者：
Seshadhri, C.