Document Open Access Logo

Finding Monotone Patterns in Sublinear Time, Adaptively

Authors Omri Ben-Eliezer , Shoham Letzter , Erik Waingarten

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.17.pdf
  • Filesize: 0.87 MB
  • 19 pages

Document Identifiers

Author Details

Omri Ben-Eliezer
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Shoham Letzter
  • University College London, UK
Erik Waingarten
  • Stanford University, CA, USA

Funding

  • Letzter, Shoham: Research supported by Dr. Max Rössler, the Walter Haefner Foundation and by the ETH Zurich Foundation.
  • Waingarten, Erik: This work is supported by the National Science Foundation under Award No. 2002201 and Moses Charikar’s Simons Investigator award.

Cite AsGet BibTex

Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten. Finding Monotone Patterns in Sublinear Time, Adaptively. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.17

Abstract

We investigate adaptive sublinear algorithms for finding monotone patterns in sequential data. Given fixed 2 ≤ k ∈ m N and ε > 0, consider the problem of finding a length-k increasing subsequence in a sequence f : [n] → ℝ, provided that f is ε-far from free of such subsequences. It was shown by Ben-Eliezer et al. [FOCS 2019] that the non-adaptive query complexity of the above task is Θ((log n)^⌊log₂ k⌋). In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes O(log n) queries. This is optimal, matching the classical Ω(log n) adaptive lower bound by Fischer [Inf. Comp. 2004] for monotonicity testing (which corresponds to the case k = 2). Equivalently, our result implies that testing whether a sequence decomposes into k monotone subsequences can be done with O(log n) queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • property testing
  • monotone patterns
  • monotone decomposition
  • adaptivity

Metrics

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

Related Versions

References

  1. Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu. Estimating the distance to a monotone function. Random Structures and Algorithms, 31(3):371-383, 2007. Google Scholar
  2. Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, and Clifford Stein. Estimating the longest increasing subsequence in nearly optimal time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2112.05106.
  3. Aleksandrs Belovs. Adaptive Lower Bound for Testing Monotonicity on the Line. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 31:1-31:10, 2018. Google Scholar
  4. Aleksandrs Belovs and Eric Blais. Quantum algorithm for monotonicity testing on the hypercube. Theory of Computing, 11(16):403-412, 2015. Google Scholar
  5. Omri Ben-Eliezer. Testing local properties of arrays. In Proceedings of the 10th Conference on Innovations in Theoretical Computer Science (ITCS), pages 11:1-11:20, 2019. Google Scholar
  6. Omri Ben-Eliezer and Clément L. Canonne. Improved bounds for testing forbidden order patterns. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2093-2112, 2018. Google Scholar
  7. Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, and Erik Waingarten. Finding monotone patterns in sublinear time. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1469-1494. IEEE Computer Society, 2019. Google Scholar
  8. Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and Counting Permutations via CSPs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  9. Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. A o(d) ⋅ polylog n monotonicity tester for boolean functions over the hypergrid [n]^d. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2133-2151, 2018. Google Scholar
  10. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  11. Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In Proceedings of the 29th Conference on Computational Complexity (CCC), pages 309-320, 2014. Google Scholar
  12. Mahdi Boroujeni and Saeed Seddighin. Improved MPC algorithms for edit distance and ulam distance. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 31-40, 2019. Google Scholar
  13. Jop Briët, Sourav Chakraborty, David García-Soriano, and Arie Matsliah. Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35-53, 2012. Google Scholar
  14. Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC), pages 419-428, 2013. Google Scholar
  15. Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10(17):453-464, 2014. Google Scholar
  16. Deeparnab Chakrabarty and C. Seshadhri. An o(n) monotonicity tester for boolean functions over the hypercube. SIAM Journal on Computing, 45(2):461-472, 2016. Google Scholar
  17. Deeparnab Chakrabarty and C Seshadhri. Adaptive boolean monotonicity testing in total influence time. In Proceedings of the 10th Conference on Innovations in Theoretical Computer Science (ITCS), pages 20:1-20:7, 2019. Google Scholar
  18. Alex Chen, Timothy Chu, and Nathan Pinsker. The dynamic longest increasing subsequence problem. arXiv preprint, 2013. URL: http://arxiv.org/abs/1309.7724.
  19. Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. In Proceedings of the 47th ACM Symposium on the Theory of Computing (STOC), pages 519-528, 2015. Google Scholar
  20. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 285-295, 2014. Google Scholar
  21. Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. In Proceedings of the 49th ACM Symposium on the Theory of Computing (STOC), pages 523-536, 2017. Google Scholar
  22. Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161-166, 1950. Google Scholar
  23. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 97-108, 1999. Google Scholar
  24. Funda Ergün and Hossein Jowhari. On the monotonicity of a data stream. Combinatorica, 35(6):641-653, 2015. Google Scholar
  25. Funda Ergün, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, and Mahesh Vishwanthan. Spot-checkers. Journal of Computer and System Sciences, 60(3):717-751, 2000. Google Scholar
  26. Chaim Even-Zohar and Calvin Leng. Counting small permutation patterns. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2288-2302, 2021. Google Scholar
  27. Eldar Fischer. On the strength of comparisons in property testing. Information and Computation, 189(1):107-116, 2004. Google Scholar
  28. Jacob Fox. Stanley-Wilf limits are typically exponential. arXiv, 2013. URL: http://arxiv.org/abs/1310-8378.
  29. Michael L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. Google Scholar
  30. Anna Gál and Parikshit Gopalan. Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence. SICOMP, 39(8):3463-3479, 2010. Short version in FOCS'07. Google Scholar
  31. Paweł Gawrychowski and Wojciech Janczewski. Fully dynamic approximation of LIS in polylogarithmic time. In Proceedings of the 53rd ACM Symposium on the Theory of Computing (STOC), pages 654-667, 2021. Google Scholar
  32. Oded Goldreich. Introduction to property testing. Cambridge University Press, 2017. Google Scholar
  33. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998. Google Scholar
  34. Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. Estimating the sortedness of a data stream. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 318-327, 2007. Google Scholar
  35. Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 82-101, 2014. Google Scholar
  36. Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th ACM Symposium on the Theory of Computing (STOC), pages 798-811, 2017. Google Scholar
  37. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric type theorems. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 52-58, 2015. Google Scholar
  38. Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley, 1968. Google Scholar
  39. Tomasz Kociumaka and Saeed Seddighin. Improved dynamic algorithms for longest increasing subsequence. In 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 640-653, 2021. Google Scholar
  40. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory, Series A, 107:153-160, 2004. Google Scholar
  41. Michael Mitzenmacher and Saeed Seddighin. Dynamic algorithms for LIS and distance to monotonicity. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC), pages 671-684, 2020. Google Scholar
  42. Michael Mitzenmacher and Saeed Seddighin. Improved sublinear time algorithm for longest increasing subsequence. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1934-1947, 2021. Google Scholar
  43. Timothy Naumovitz and Michael E. Saks. A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1252-1262, 2015. Google Scholar
  44. Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1582-1597, 2017. Google Scholar
  45. Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array. Random Structures and Algorithms, 55:402-426, 2019. Extended abstract in SODA 2017 [Ilan Newman et al., 2017]. Google Scholar
  46. Ilan Newman and Nithin Varma. New sublinear algorithms and lower bounds for LIS estimation. In 48th International Colloquium on Automata, Languages, and Programming (ICALP), pages 100:1-100:20, 2021. URL: http://arxiv.org/abs/2010.05805.
  47. Ilan Newman and Nitin Varma. Strongly sublinear algorithms for testing pattern freeness. arXiv preprint, 2021. To appear in ICALP 2022. URL: http://arxiv.org/abs/2106.04856.
  48. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin M. Varma. Parameterized property testing of functions. ACM Transactions on Computation Theory, 9(4):17:1-17:19, 2018. Google Scholar
  49. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012-1042, 2006. Google Scholar
  50. Prakash Ramanan. Tight ω(n log n) lower bound for finding a longest increasing subsequence. International Journal of Computer Mathematics, 65(3-4):161-164, 1997. Google Scholar
  51. Ronitt Rubinfeld and Madhu Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  52. Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. Approximation algorithms for LCS and LIS with truly improved running times. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1121-1145. IEEE Computer Society, 2019. Google Scholar
  53. Michael Saks and C. Seshadhri. Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1698-1709, 2013. Google Scholar
  54. Michael E. Saks and C. Seshadhri. Estimating the longest increasing sequence in polylogarithmic time. SIAM J. Comput., 46(2):774-823, 2017. Short version in FOCS 2010. Google Scholar
  55. Rodica Simion and Frank W. Schmidt. Restricted permutations. European Journal of Combinatorics, 6(4):383-406, 1985. Google Scholar
  56. Xiaoming Sun and David P. Woodruff. The communication and streaming complexity of computing the longest common and increasing subsequences. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 336-345, 2007. Google Scholar
  57. Vincent Vatter. Permutation classes. In Handbook of Enumerative Combinatorics, pages 777-858. Chapman and Hall/CRC, 2015. 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