Document Open Access Logo

Strongly Sublinear Algorithms for Testing Pattern Freeness

Authors Ilan Newman, Nithin Varma

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.98.pdf
  • Filesize: 0.75 MB
  • 20 pages

Document Identifiers

Author Details

Ilan Newman
  • Department of Computer Science, University of Haifa, Israel
Nithin Varma
  • Chennai Mathematical Institute, India

Funding

  • Newman, Ilan: The author was supported by the Israel Science Foundation, grant number 379/21.

Cite AsGet BibTex

Ilan Newman and Nithin Varma. Strongly Sublinear Algorithms for Testing Pattern Freeness. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 98:1-98:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.98

Abstract

For a permutation π:[k] → [k], a function f:[n] → ℝ contains a π-appearance if there exists 1 ≤ i₁ < i₂ < … < i_k ≤ n such that for all s,t ∈ [k], f(i_s) < f(i_t) if and only if π(s) < π(t). The function is π-free if it has no π-appearances. In this paper, we investigate the problem of testing whether an input function f is π-free or whether f differs on at least ε n values from every π-free function. This is a generalization of the well-studied monotonicity testing and was first studied by Newman, Rabinovich, Rajendraprasad and Sohler [Ilan Newman et al., 2019]. We show that for all constants k ∈ ℕ, ε ∈ (0,1), and permutation π:[k] → [k], there is a one-sided error ε-testing algorithm for π-freeness of functions f:[n] → ℝ that makes Õ(n^o(1)) queries. We improve significantly upon the previous best upper bound O(n^{1 - 1/(k-1)}) by Ben-Eliezer and Canonne [Omri Ben-Eliezer and Clément L. Canonne, 2018]. Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Property testing
  • Pattern freeness
  • Sublinear algorithms

Metrics

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

Related Versions

References

  1. Shlomo Ahal and Yuri Rabinovich. On complexity of the subpattern problem. SIAM J. Discret. Math., 22(2):629-649, 2008. URL: https://doi.org/10.1137/S0895480104444776.
  2. Michael H. Albert, Robert E. L. Aldred, Mike D. Atkinson, and Derek A. Holton. Algorithms for pattern involvement in permutations. In Peter Eades and Tadao Takaoka, editors, Algorithms and Computation, 12th International Symposium, ISAAC 2001, Proceedings, volume 2223 of Lecture Notes in Computer Science, pages 355-366. Springer, 2001. Google Scholar
  3. Noga Alon and Ehud Friedgut. On the number of permutations avoiding a given pattern. J. Comb. Theory, Ser. A, 89(1):133-140, 2000. URL: https://doi.org/10.1006/jcta.1999.3002.
  4. Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular languages are testable with a constant number of queries. SIAM J. Comput., 30(6):1842-1862, 2000. URL: https://doi.org/10.1137/S0097539700366528.
  5. Richard Arratia. On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. The Electronic Journal of Combinatorics, 6:1-4, 1999. Google Scholar
  6. Aleksandrs Belovs. Adaptive lower bound for testing monotonicity on the line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, pages 31:1-31:10, 2018. Google Scholar
  7. Omri Ben-Eliezer and Clément L. Canonne. Improved bounds for testing forbidden order patterns. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2093-2112. SIAM, 2018. Google Scholar
  8. Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, and Erik Waingarten. Finding monotone patterns in sublinear time. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 1469-1494. IEEE Computer Society, 2019. Google Scholar
  9. Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten. Optimal adaptive detection of monotone patterns. CoRR, abs/1911.01169, 2019. URL: http://arxiv.org/abs/1911.01169.
  10. Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and counting permutations via CSPs. Algorithmica, pages 1-26, 2021. Google Scholar
  11. Donald J. Berndt and James Clifford. Using dynamic time warping to find patterns in time series. In Usama M. Fayyad and Ramasamy Uthurusamy, editors, Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, 1994. Technical Report WS-94-03, pages 359-370. AAAI Press, 1994. Google Scholar
  12. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners. SIAM Journal on Computing, 41(6):1380-1425, 2012. URL: https://doi.org/10.1137/110826655.
  13. Miklós Bóna. Exact and asymptotic enumeration of permutations with subsequence conditions. PhD thesis, Massachusetts Institute of Technology, 1997. Google Scholar
  14. Miklós Bóna. The solution of a conjecture of Stanley and Wilf for all layered patterns. J. Comb. Theory, Ser. A, 85(1):96-104, 1999. URL: https://doi.org/10.1006/jcta.1998.2908.
  15. Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proceedings of the ACM Symposium on Theory of Computing (STOC) 2013, pages 419-428, 2013. Google Scholar
  16. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-resilient property testing. SIAM J. Comput., 47(2):295-329, 2018. URL: https://doi.org/10.1137/16M1075661.
  17. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In RANDOM-APPROX, 1999, Proceedings, pages 97-108, 1999. Google Scholar
  18. Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan. Spot-checkers. Journal of Computer and System Sciences, 60(3):717-751, 2000. URL: https://doi.org/10.1006/jcss.1999.1692.
  19. Eldar Fischer. On the strength of comparisons in property testing. Inf. Comput., 189(1):107-116, 2004. URL: https://doi.org/10.1016/j.ic.2003.09.003.
  20. Jacob Fox. Stanley-Wilf limits are typically exponential. CoRR, abs/1310.8378, 2013. URL: http://arxiv.org/abs/1310.8378.
  21. Jacob Fox and Fan Wei. Fast property testing and metrics for permutations. Comb. Probab. Comput., 27(4):539-579, 2018. URL: https://doi.org/10.1017/S096354831800024X.
  22. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  23. Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 82-101. SIAM, 2014. Google Scholar
  24. Eamonn J. Keogh, Stefano Lonardi, and Bill Yuan-chi Chiu. Finding surprising patterns in a time series database in linear time and space. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, pages 550-556. ACM, 2002. Google Scholar
  25. Martin Klazar. The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture. In Formal power series and algebraic combinatorics, pages 250-255. Springer, 2000. Google Scholar
  26. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. J. Comb. Theory, Ser. A, 107(1):153-160, 2004. URL: https://doi.org/10.1016/j.jcta.2004.04.002.
  27. Michael Mitzenmacher and Saeed Seddighin. Improved sublinear time algorithm for longest increasing subsequence. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 1934-1947. SIAM, 2021. Google Scholar
  28. Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array. Random Struct. Algorithms, 55(2):402-426, 2019. URL: https://doi.org/10.1002/rsa.20840.
  29. Ilan Newman and Nithin Varma. New sublinear algorithms and lower bounds for LIS estimation. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 100:1-100:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  30. Ilan Newman and Nithin Varma. Strongly sublinear algorithms for testing pattern freeness. CoRR, abs/2106.04856, 2021. URL: http://arxiv.org/abs/2106.04856.
  31. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized property testing of functions. ACM Trans. Comput. Theory, 9(4):17:1-17:19, 2018. URL: https://doi.org/10.1145/3155296.
  32. Pranav Patel, Eamonn J. Keogh, Jessica Lin, and Stefano Lonardi. Mining motifs in massive time series databases. In Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002), pages 370-377. IEEE Computer Society, 2002. Google Scholar
  33. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: https://doi.org/10.1137/S0097539793255151.
  34. Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. Approximation algorithms for LCS and LIS with truly improved running times. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 1121-1145, 2019. Google Scholar
  35. Michael E. Saks and C. Seshadhri. Estimating the longest increasing sequence in polylogarithmic time. SIAM Journal on Computing, 46(2):774-823, 2017. 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 Imprint Privacy Contact