1 Search Results for "Swartworth, William J."

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.44
Testing Hereditary Properties of Sequences

Authors: Cody R. Freitag, Eric Price, and William J. Swartworth

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

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.
Cite as

Cody R. Freitag, Eric Price, and William J. Swartworth. Testing Hereditary Properties of Sequences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 44:1-44:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{freitag_et_al:LIPIcs.APPROX-RANDOM.2017.44,
  author =	{Freitag, Cody R. and Price, Eric and Swartworth, William J.},
  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 =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.44},
  URN =		{urn:nbn:de:0030-drops-75938},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.44},
  annote =	{Keywords: Property Testing}
}
  • Refine by Author
  • 1 Freitag, Cody R.
  • 1 Price, Eric
  • 1 Swartworth, William J.

  • Refine by Classification

  • Refine by Keyword
  • 1 Property Testing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact