Estimating the longest increasing sequence in polylogarithmic time
type: Item
instance of: scholarly article
title: Estimating the Longest Increasing Sequence in Polylogarithmic Time
zbMATH Open document ID: 1370.68342
DOI: 10.1137/130942152
author: C. Seshadhri
author: Michael Saks
published in: SIAM Journal on Computing
publication date: 2017-05-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1308.0626
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6724223
zbMATH Keywords: longest increasing sequence
zbMATH Keywords: sublinear algorithms
zbMATH Keywords: property testing
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2606114621
cites work: Estimating the distance to a monotone function
cites work: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
cites work: Q4633899
cites work: The computational hardness of estimating edit distance
cites work: The smoothed complexity of edit distance
cites work: Near-optimal sublinear time algorithms for Ulam distance
cites work: Transitive-closure spanners
cites work: Introduction to algorithms
cites work: Q4941829
cites work: Concentration of Measure for the Analysis of Randomized Algorithms
cites work: Q3579382
cites work: Spot-checkers
cites work: Q3152421
cites work: Monotonicity testing over general poset domains
cites work: On computing the length of longest increasing subsequences
cites work: Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
cites work: Q4224925
cites work: Testing monotonicity
cites work: Property testing and its connection to learning and approximation
cites work: Estimating the sortedness of a data stream
cites work: Distribution-Free Property-Testing
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Tolerant property testing and distance approximation
cites work: Q4788610
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
cites work: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
cites work: The communication and streaming complexity of computing the longest common and increasing subsequences
Recommended article: Estimating the sortedness of a data stream
Recommended article: Fast computation of a longest increasing subsequence and application
Recommended article: Space-efficient algorithms for longest increasing subsequence
Recommended article: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
description: scientific article; zbMATH DE number 6724223