Property Testing: Problems and Techniques
Property Testing: Problems and Techniques
复制标题
性能测试：问题和技术
DOI：
10.1007/978-981-16-8622-1
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Y. Yoshida
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;Y. Yoshida
属性测试是一个新兴的领域，其目标是确定输入是否满足输入大小的次线性时间或甚至恒定时间（即独立于输入大小）的预定属性的算法。当然，如果不阅读整个输入，我们无法在次线性时间内正确解决问题;因此，我们需要一些假设或妥协。首先，我们假设对输入的查询访问是可用的，通过它我们可以在恒定的时间内获得一小部分输入。第二，我们与近似决策妥协;也就是说，我们只针对算法，区分满足预定属性的输入从那些远远不满足它，这样的算法被称为测试的属性，它已被证明在过去的几十年中，有许多属性的各种对象，如字符串，图形和函数的次线性时间测试。本书的第一个目标是向广大读者介绍属性测试中的重要结果和技术。为了设计高效的测试器并证明其正确性，我们将利用与数学和计算机科学其他领域的各种联系，例如组合学，图论，拟阵理论，计算学习理论和编码理论。我们希望读者能够欣赏到这些连接是多么漂亮，它们被用于设计和分析属性测试程序。这本书的第二个目标是展示常数查询可测试性质的特征，这些性质已经为（稠密）图、有限域上的函数和约束满足问题（CSP）获得。显示这些特征的一个原因是它们的内在价值：它们本身就是令人惊讶的基本结果。另一个原因是，通过对这些特征的讨论，我们可以深入了解constantquery测试人员实际测试的内容。例如，有限域上的图和函数的特征是从一般分解结果导出的，它将图或函数分解为结构部分和伪随机部分，在适当的意义下。在这里，我们借用的结果开发添加剂组合。另一个已知的特征是用于测试对CSP实例的分配是否是令人满意的分配。在这里，我们将VII
Property testing is an emerging area that aims for algorithms that decide whether the input satisfies a predetermined property in sublinear time in the input size, or even in constant time, that is, independent of the input size. Of course, we cannot correctly solve problems in sublinear time without reading the whole input; so, we need several assumptions or compromises. First, we assume that query access to the input is available through which we can get a small part of the input in constant time. Second, we compromise with approximate decisions; that is, we only aim for algorithms that distinguish inputs satisfying the predetermined property from those that are far from satisfying it. Such algorithms are called testers for the property, and it has been shown in the past few decades that there are sublinear-time testers for many properties on various objects such as strings, graphs, and functions. The first goal of this book is to introduce important results and techniques in property testing to a broad audience. To design efficient testers and show their correctness, we will make use of a variety of connections to other areas of mathematics and computer science, such as combinatorics, graph theory, matroid theory, computational learning theory, and coding theory. We hope that the reader appreciates how beautifully these connections are employed for the purpose of designing and analyzing property testers. The second goal of this book is to show characterizations of constant-query testable properties, which have been obtained for (dense) graphs, functions over finite fields, and constraint satisfaction problems (CSPs). One reason for showing such characterizations is their intrinsic value: they themselves are surprising and fundamental results. Another reason is that, through the arguments toward those characterizations, we can get insights into what constantquery testers actually test. For example, the characterizations for graphs and functions over finite fields are derived from general decomposition results, which decompose graphs or functions into the structured part and the pseudorandom part in a suitable sense. Here, we borrow results developed in additive combinatorics. Another characterization is known for testing whether an assignment to a CSP instance is a satisfying assignment. Here, we will vii