Cell-probe lower bounds for bit stream computation

DOI10.4230/LIPICS.ESA.2016.31MaRDI QIDQ4606300zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Publication date 2 March 2018

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.ESA.2016.31

zbMATH Keywords

algorithmsdata streamingcell-probe lower bounds

Mathematics Subject Classification ID

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

Recommendations

• Cell-probe bounds for online edit distance and other pattern matching problems
• Tight Cell-Probe Bounds for Online Hamming Distance Computation
• Time bounds for streaming problems
• Space Lower Bounds for Online Pattern Matching
• Space lower bounds for online pattern matching

Cited in

(5)

• Cell-probe bounds for online edit distance and other pattern matching problems
• Time bounds for streaming problems
• Automata, Languages and Programming
• Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
• On the cell probe complexity of polynomial evaluation

This page was built for publication: Cell-probe lower bounds for bit stream computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606300)