On the cell probe complexity of polynomial evaluation

DOI10.1016/0304-3975(95)80032-5zbMath0873.68093OpenAlexW2144518319MaRDI QIDQ673647

Peter Bro Miltersen

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)80032-5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

The cell probe complexity of succinct data structures ⋮ On dynamic bit-probe complexity ⋮ The function-inversion problem: barriers and opportunities ⋮ Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds ⋮ Bounded-depth circuits cannot sample good codes ⋮ On data structures and asymmetric communication complexity

Cites Work

• Unnamed Item
• A lower bound for finding predecessors in Yao's cell probe model
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Complexity models for incremental computation
• Lower bounds for union-split-find related problems on random access machines
• Hash functions for priority queues
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Should Tables Be Sorted?

This page was built for publication: On the cell probe complexity of polynomial evaluation