Time bounds for streaming problems

DOI10.4086/TOC.2019.V015A002MaRDI QIDQ5204820zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Publication date 5 December 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1412.6935

zbMATH Keywords

cell probelower boundsonline algorithmsstreaming algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

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

Cited in

(9)

• Characterizing polynomial time complexity of stream programs using interpretations
• On the complexity of stream equality
• Streaming Algorithms Measured in Terms of the Computed Quantity
• Cell-probe lower bounds for bit stream computation
• Faster Update Time for Turnstile Streaming Algorithms
• Cell-probe bounds for online edit distance and other pattern matching problems
• Streaming Lower Bounds for Approximating MAX-CUT
• scientific article; zbMATH DE number 7651106 (Why is no real title available?)
• Streaming algorithms for bin packing and vector scheduling

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)