Time bounds for streaming problems
From MaRDI portal
Publication:5204820
DOI10.4086/TOC.2019.V015A002zbMATH Open1477.68543arXiv1412.6935OpenAlexW2981423113MaRDI QIDQ5204820FDOQ5204820
Authors: Raphaël Clifford, Markus Jalsenius, Benjamin Sach 
Publication date: 5 December 2019
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.6935
Recommendations
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
- Cell-probe lower bounds for bit stream computation
- Tight Cell-Probe Bounds for Online Hamming Distance Computation
- Cell-probe bounds for online edit distance and other pattern matching problems
- Approximate Hamming distance in a stream
Online algorithms; streaming algorithms (68W27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (9)
- Cell-probe bounds for online edit distance and other pattern matching problems
- Characterizing polynomial time complexity of stream programs using interpretations
- Cell-probe lower bounds for bit stream computation
- Streaming algorithms for bin packing and vector scheduling
- Faster Update Time for Turnstile Streaming Algorithms
- Streaming Lower Bounds for Approximating MAX-CUT
- Title not available (Why is that?)
- On the complexity of stream equality
- Streaming Algorithms Measured in Terms of the Computed Quantity
This page was built for publication: Time bounds for streaming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204820)
