License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.44
URN: urn:nbn:de:0030-drops-75938
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7593/
Freitag, Cody R. ;
Price, Eric ;
Swartworth, William J.
Testing Hereditary Properties of Sequences
Abstract
A hereditary property of a sequence is one that is preserved when restricting to subsequences. We show that there exist hereditary properties of sequences that cannot be tested with sublinear queries, resolving an open question posed by Newman et al. This proof relies crucially on an infinite alphabet, however; for finite alphabets, we observe that any hereditary property can be tested with a constant number of queries.
BibTeX - Entry
@InProceedings{freitag_et_al:LIPIcs:2017:7593,
author = {Cody R. Freitag and Eric Price and William J. Swartworth},
title = {{Testing Hereditary Properties of Sequences}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {44:1--44:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7593},
URN = {urn:nbn:de:0030-drops-75938},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.44},
annote = {Keywords: Property Testing}
}
|
Keywords: |
|
Property Testing |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
