1 Search Results for "Fahey, Polly"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2020.7

Faster Property Testers in a Variation of the Bounded Degree Model

Authors: Isolde Adler and Polly Fahey

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract

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.

Cite as

Isolde Adler and Polly Fahey. Faster Property Testers in a Variation of the Bounded Degree Model. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{adler_et_al:LIPIcs.FSTTCS.2020.7,
  author =	{Adler, Isolde and Fahey, Polly},
  title =	{{Faster Property Testers in a Variation of the Bounded Degree Model}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.7},
  URN =		{urn:nbn:de:0030-drops-132482},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.7},
  annote =	{Keywords: Constant Time Algorithms, Logic and Databases, Property Testing, Bounded Degree Model}
}

Refine by Author
1 Adler, Isolde
1 Fahey, Polly

Refine by Classification
1 Theory of computation → Database query processing and optimization (theory)
1 Theory of computation → Streaming, sublinear and near linear time algorithms

Refine by Keyword
1 Bounded Degree Model
1 Constant Time Algorithms
1 Logic and Databases
1 Property Testing

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Fahey, Polly"

Faster Property Testers in a Variation of the Bounded Degree Model

Abstract

Cite as

Thanks for your feedback!

Could not send message