Estimating the Longest Increasing Sequence in Polylogarithmic Time

DOI10.1137/130942152zbMath1370.68342arXiv1308.0626OpenAlexW2606114621MaRDI QIDQ5737810

C. Seshadhri, Michael E. Saks

Publication date: 30 May 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.0626

zbMATH Keywords

property testingsublinear algorithmslongest increasing sequence

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items

On the monotonicity of a data stream, Space-Efficient Algorithms for Longest Increasing Subsequence, Improved algorithm for permutation testing, Erasure-Resilient Property Testing, Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems, Space-efficient algorithms for longest increasing subsequence, Estimating the Longest Increasing Sequence in Polylogarithmic Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the length of longest increasing subsequences
• Spot-checkers
• Tolerant property testing and distance approximation
• The Computational Hardness of Estimating Edit Distance
• Property testing and its connection to learning and approximation
• The smoothed complexity of edit distance
• Distribution-Free Property-Testing
• Monotonicity testing over general poset domains
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Robust Characterizations of Polynomials with Applications to Program Testing
• Transitive-Closure Spanners
• Probability Inequalities for Sums of Bounded Random Variables
• Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
• Estimating the distance to a monotone function
• Estimating the Longest Increasing Sequence in Polylogarithmic Time
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Concentration of Measure for the Analysis of Randomized Algorithms
• Testing monotonicity