论文标题
限制度模型的变化速度更快的属性测试仪
Faster Property Testers in a Variation of the Bounded Degree Model
论文作者
论文摘要
属性测试算法是高效的算法，它具有概率准确性的保证。对于属性P，目标是通过仅查询输入的少量本地部分来区分p与p正确概率正确的输入。在图表上的属性测试中，距离是通过边缘修改的数量（添加或删除）来测量的，这些距离（添加或删除）将图形转换为具有属性的图形所必需的。许多研究都集中在此类算法的查询复杂性上。 e。算法对输入的查询数量，但是鉴于应用程序，该算法的运行时间同样相关。 在（Adler，Harwath Stacs 2018）中，引入了界限度测试的有限程度图模型的自然扩展到有限程度的关系数据库，并且显示出，在有界程度和有限的树宽的数据库中，每个在单声道二阶逻辑中都能与计数（CMSO）相关的每个属性都具有恒定效率和常量性的运行量，并且可以进行稳定的效率。是否可以将其改进到持续的运行时间，保持开放。 在本文中，我们介绍了一个基于有界度模型的新模型，但是距离度量允许边缘（元组）修改和顶点（元素）修改。我们的主要定理表明，在有界程度和有限的树宽的数据库上，在CMSO中表达的每个属性都是可测试的，具有恒定的查询复杂性和新模型中恒定的运行时间。我们还表明，在经典模型中可测试的每个属性都可以在我们的模型中具有相同的查询复杂性和运行时间测试，但是相反的是不正确的。 我们认为我们的模型是自然的，我们的元理论表现出恒定的CMSO可验证性支持了这一点。
Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions), that are necessary to transform a graph into one with property P. Much research has focussed on the query complexity of such algorithms, i. e. the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this paper we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. We also show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.
