Streaming and query once space complexity of longest increasing subsequence
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3890736 (Why is no real title available?)
- scientific article; zbMATH DE number 5764793 (Why is no real title available?)
- scientific article; zbMATH DE number 3919835 (Why is no real title available?)
- scientific article; zbMATH DE number 549860 (Why is no real title available?)
- scientific article; zbMATH DE number 1405644 (Why is no real title available?)
- scientific article; zbMATH DE number 3373691 (Why is no real title available?)
- scientific article; zbMATH DE number 7788453 (Why is no real title available?)
- scientific article; zbMATH DE number 7799605 (Why is no real title available?)
- A Lower Bound for Integer Multiplication with Read-Once Branching Programs
- A lower bound for integer multiplication on randomized ordered read-once branching programs.
- A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
- A read-once branching program lower bound of \({\omega}(2^{n/4})\) for integer multiplication using universal hashing
- A simple function that requires exponential size read-once branching programs
- A very simple function that requires exponential size read-once branching programs.
- Almost \(k\)-wise independence and hard Boolean functions.
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Communication complexity (for algorithm designers)
- Dynamic algorithms for LIS and distance to monotonicity
- Efficient massively parallel methods for dynamic programming
- Entropy of contact circuits and lower bounds on their complexity
- Estimating the longest increasing sequence in polylogarithmic time
- Estimating the sortedness of a data stream
- Fully dynamic approximation of LIS in polylogarithmic time
- Improved dynamic algorithms for longest increasing subsequence
- Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
- On lower bounds for read-\(k\)-times branching programs
- On the complexity of branching programs and decision trees for clique functions
- Relationships between nondeterministic and deterministic tape complexities
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
- Space-efficient algorithms for longest increasing subsequence
- The communication and streaming complexity of computing the longest common and increasing subsequences
- The randomized communication complexity of set disjointness
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)
