Document Open Access Logo

Testing Hereditary Properties of Sequences

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.44.pdf
  • Filesize: 429 kB
  • 10 pages

Document Identifiers

Author Details

Cody R. Freitag
Eric Price
William J. Swartworth

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.44

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.

Subject Classification

Keywords
  • Property Testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Omri Ben-Eliezer, and Eldar Fischer. Testing hereditary properties of ordered graphs and matrices. arXiv preprint arXiv:1704.02367, 2017. Google Scholar
  2. Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing, 37(6):1703-1727, 2008. Google Scholar
  3. Tim Austin and Terence Tao. Testability and repair of hereditary hypergraph properties. Random Structures &Algorithms, 36(4):373-463, 2010. Google Scholar
  4. Antônio J. O. Bastos, Carlos Hoppen, Yoshiharu Kohayakawa, and Rudini M. Sampaio. Every hereditary permutation property is testable. Electronic Notes in Discrete Mathematics, 38:123-128, 2011. Google Scholar
  5. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners. SIAM Journal on Computing, 41(6):1380-1425, 2012. Google Scholar
  6. Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig. Quantum property testing. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 480-488. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  7. Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 419-428. ACM, 2013. Google Scholar
  8. Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 425-435. Springer, 2013. Google Scholar
  9. Artur Czumaj, Asaf Shapira, and Christian Sohler. Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, 38(6):2499-2510, 2009. Google Scholar
  10. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques, pages 97-108. Springer, 1999. Google Scholar
  11. Eldar Fischer. On the strength of comparisons in property testing. Information and Computation, 189(1):107-116, 2004. Google Scholar
  12. Jacob Fox. Stanley-wilf limits are typically exponential. arXiv preprint arXiv:1310.8378, 2013. Google Scholar
  13. Oded Goldreich. Combinatorial property testing (a survey). Randomization Methods in Algorithm Design, 43:45-59, 1999. Google Scholar
  14. Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  15. Leonard H. Haines. On free monoids partially ordered by embedding. Journal of Combinatorial Theory, 6(1):94-98, 1969. Google Scholar
  16. Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, and Rudini Menezes Sampaio. Testing permutation properties through subpermutations. Theoretical Computer Science, 412(29):3555-3567, 2011. Google Scholar
  17. Tereza Klimošová and Daniel Král. Hereditary properties of permutations are strongly testable. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1164-1173. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  18. Joseph B. Kruskal. The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A, 13(3):297-305, 1972. Google Scholar
  19. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the stanley-wilf conjecture. Journal of Combinatorial Theory, Series A, 107(1):153-160, 2004. Google Scholar
  20. Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1582-1597. SIAM, 2017. Google Scholar
  21. Daniel A Spielman and Miklós Bóna. An infinite antichain of permutations. Electron. J. Combin, 7:N2, 2000. Google Scholar
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 About DROPS Imprint Privacy Contact