Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model

DOI10.1007/978-3-642-22006-7_50zbMath1333.68121OpenAlexW1900852564MaRDI QIDQ3012835

Raphaël Clifford, Markus Jalsenius

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://research-information.bris.ac.uk/en/publications/4f6ef888-d727-40ae-9f58-8b15dc3ad4e1

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Lower Bounds for Multiplication via Network Coding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern matching in pseudo real-time
• Distribution of Bordered Persymmetric Matrices in a Finite Field.
• A Black Box for Online Approximate Pattern Matching
• String Matching in Real Time
• Should Tables Be Sorted?
• Logarithmic Lower Bounds in the Cell-Probe Model
• Fast on-line integer multiplication

This page was built for publication: Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model