Streaming and query once space complexity of longest increasing subsequence

DOI10.1007/978-3-031-49190-0_3MaRDI QIDQ6591455

Xin Li, Yu Zheng

Publication date: 22 August 2024

zbMATH Keywords

approximation algorithmbranching programlongest increasing subsequencestreaming algorithm

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A simple function that requires exponential size read-once branching programs
• Entropy of contact circuits and lower bounds on their complexity
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Almost \(k\)-wise independence and hard Boolean functions.
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• Space-efficient algorithms for longest increasing subsequence
• On lower bounds for read-\(k\)-times branching programs
• Relationships between nondeterministic and deterministic tape complexities
• A very simple function that requires exponential size read-once branching programs.
• Communication Complexity (for Algorithm Designers)
• On the complexity of branching programs and decision trees for clique functions
• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• Efficient massively parallel methods for dynamic programming
• Dynamic algorithms for LIS and distance to monotonicity
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
• Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
• Estimating the Longest Increasing Sequence in Polylogarithmic Time
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Improved dynamic algorithms for longest increasing subsequence
• Fully dynamic approximation of LIS in polylogarithmic time

This page was built for publication: Streaming and query once space complexity of longest increasing subsequence

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