Streaming and query once space complexity of longest increasing subsequence
From MaRDI portal
Publication:6591455
DOI10.1007/978-3-031-49190-0_3MaRDI QIDQ6591455
Publication date: 22 August 2024
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)