License
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://drops.dagstuhl.de/opus/volltexte/2017/7593/
Go to the corresponding LIPIcs Volume Portal


Freitag, Cody R. ; Price, Eric ; Swartworth, William J.

Testing Hereditary Properties of Sequences

pdf-format:
LIPIcs-APPROX-RANDOM-2017-44.pdf (0.4 MB)


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
Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 31.07.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI