Estimating the Longest Increasing Sequence in Polylogarithmic Time
From MaRDI portal
Publication:5737810
DOI10.1137/130942152zbMath1370.68342arXiv1308.0626OpenAlexW2606114621MaRDI QIDQ5737810
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
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