New sublinear algorithms and lower bounds for LIS estimation

DOI10.4230/LIPICS.ICALP.2021.100MaRDI QIDQ7241200zbMATH OpenFDO

Authors Ilan Newman, Nithin K. Varma

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.100

zbMATH Keywords

distance estimationlongest increasing subsequencemonotonicitysublinear algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• L_p-testing
• Adaptive lower bound for testing monotonicity on the line
• Approximation algorithms for LCS and LIS with truly improved running times
• Erasure-Resilient Property Testing
• Erasures vs. errors in local decoding and property testing
• Estimating the distance to a monotone function
• Estimating the longest increasing sequence in polylogarithmic time
• Finding monotone patterns in sublinear time
• scientific article; zbMATH DE number 7788453 (Why is no real title available?)
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• On computing the length of longest increasing subsequences
• On the strength of comparisons in property testing
• Parameterized property testing of functions
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Spot-checkers
• Testing for forbidden order patterns in an array
• Tolerant property testing and distance approximation

This page was built for publication: New sublinear algorithms and lower bounds for LIS estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241200)