Dynamic algorithms for LIS and distance to monotonicity

DOI10.1145/3357713.3384240MaRDI QIDQ5144953zbMATH OpenOpenAlexFDO

Authors S. Seddighin, Michael Mitzenmacher

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3357713.3384240

zbMATH Keywords

distance to monotonicitydynamicLISsublinear

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(3)

• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Streaming and query once space complexity of longest increasing subsequence
• Approximation algorithms for LCS and LIS with truly improved running times

This page was built for publication: Dynamic algorithms for LIS and distance to monotonicity

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