Space Lower Bounds for Online Pattern Matching
From MaRDI portal
Publication:3011853
DOI10.1007/978-3-642-21458-5_17zbMath1339.68103arXiv1106.4412OpenAlexW2570526021MaRDI QIDQ3011853
Raphaël Clifford, Markus Jalsenius, Benjamin Sach, Ely Porat
Publication date: 29 June 2011
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1106.4412
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)
Cites Work
- Unnamed Item
- The communication complexity of the Hamming distance problem
- Faster pattern matching with character classes using prime number encoding
- Private vs. common random bits in communication complexity
- String matching under a general matching relation
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Pattern Matching with Swaps
- Maintaining Stream Statistics over Sliding Windows
- Communication Complexity
- Exact and Approximate Pattern Matching in the Streaming Model
This page was built for publication: Space Lower Bounds for Online Pattern Matching
