Document Open Access Logo

New Sublinear Algorithms and Lower Bounds for LIS Estimation

Authors Ilan Newman, Nithin Varma

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.100.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Ilan Newman
  • University of Haifa, Israel
Nithin Varma
  • University of Haifa, Israel

Funding

  • Newman, Ilan: Supported by The Israel Science Foundation, grant number 497/17.
  • Varma, Nithin: Supported by The Israel Science Foundation, grant number 497/17 and by the PBC Fellowship for Postdoctoral Fellows by the Israeli Council of Higher Education.

Cite AsGet BibTex

Ilan Newman and Nithin Varma. New Sublinear Algorithms and Lower Bounds for LIS Estimation. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 100:1-100:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.100

Abstract

Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. Despite the significance of the LIS estimation problem and the amount of attention it has received, there are important aspects of the problem that are not yet fully understood. There are no better lower bounds for LIS estimation than the obvious bounds implied by testing monotonicity (for adaptive or nonadaptive algorithms). In this paper, we give the first nontrivial lower bound on the complexity of LIS estimation, and also provide novel algorithms that complement our lower bound. Specifically, we show that for every ε ∈ (0,1), every nonadaptive algorithm that outputs an estimate of the LIS length in an array of length n to within an additive error of ε n has to make log^{Ω(log (1/ε))} n queries. Next, we design nonadaptive LIS estimation algorithms whose complexity decreases as the number of distinct values, r, in the array decreases. We first present a simple algorithm that makes Õ(r/ε³) queries and approximates the LIS length with an additive error bounded by ε n. This algorithm has better complexity than the best previously known adaptive algorithm (Saks and Seshadhri; 2017) for the same problem when r ≪ polylog (n). We use our algorithm to construct a nonadaptive algorithm with query complexity Õ(√r⋅ poly(1/λ)) that, when the LIS is of length at least λ n, outputs a multiplicative Ω(λ)-approximation to the LIS length. Our algorithm improves upon the state of the art nonadaptive LIS estimation algorithm (Rubinstein, Seddighin, Song, and Sun; 2019) in terms of the approximation guarantee. Finally, we present a O(log n)-query nonadaptive erasure-resilient tester for monotonicity. Our result implies that lower bounds on erasure-resilient testing of monotonicity does not give good lower bounds for LIS estimation. It also implies that nonadaptive tolerant testing is strictly harder than nonadaptive erasure-resilient testing for the natural property of monotonicity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • longest increasing subsequence
  • monotonicity
  • distance estimation
  • sublinear algorithms

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 & Algorithms, 31(3):371-383, 2007. URL: https://doi.org/10.1002/rsa.20167.
  2. David Aldous and Persi Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc., 34:413-432, 1999. URL: https://doi.org/10.1090/S0273-0979-99-00796-X.
  3. 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. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.31.
  4. Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, and Erik Waingarten. Finding monotone patterns in sublinear time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 1469-1494, 2019. URL: https://doi.org/10.1109/FOCS.2019.000-1.
  5. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, pages 164-173. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591887.
  6. 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.
  7. 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. Google Scholar
  8. 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.
  9. Michael L. Fredman. On computing the length of longest increasing subsequences. Discret. Math., 11(1):29-35, 1975. URL: https://doi.org/10.1016/0012-365X(75)90103-X.
  10. 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
  11. 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, Virtual Conference, January 10 - 13, 2021, pages 1934-1947. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.115.
  12. 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. Google Scholar
  13. Ilan Newman and Nithin Varma. New sublinear algorithms and lower bounds for LIS estimation. CoRR, abs/2010.05805, 2021. URL: http://arxiv.org/abs/2010.05805.
  14. 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.
  15. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 6(72):1012-1042, 2006. Google Scholar
  16. Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin M. Varma. Erasures vs. errors in local decoding and property testing. In Proceedings of the Innovations in Theoretical Computer Science Conference, (ITCS) 2019, pages 63:1-63:21, 2019. Google Scholar
  17. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  18. 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. URL: https://doi.org/10.1109/FOCS.2019.00071.
  19. 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