On dynamic bit-probe complexity

DOI10.1016/J.TCS.2007.02.058MaRDI QIDQ2373742zbMATH OpenOpenAlexFDO

Authors Mihai Patrascu, Corina E. Tarnita

Publication date 16 July 2007

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

Full work available at URL https://doi.org/10.1016/j.tcs.2007.02.058

zbMATH Keywords

bit-probe complexitycell-probe complexitylower bounds

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Automata, Languages and Programming
• Logarithmic Lower Bounds in the Cell-Probe Model
• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
• Lower bounds for dynamic connectivity
• On the cell probe complexity of dynamic membership

Cites work

• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• Complexity models for incremental computation
• Dynamic word problems
• Logarithmic Lower Bounds in the Cell-Probe Model
• Near-optimal fully-dynamic graph connectivity
• On dynamic range reporting in one dimension
• On the cell probe complexity of polynomial evaluation
• The buffer tree: A technique for designing batched external data structures
• The Complexity of Maintaining an Array and Computing Its Partial Sums

Cited in

(16)

• Saving probe bits by cube domination
• On the fastest Vickrey algorithm
• On the complexity of non-unique probe selection
• A Survey of Data Structures in the Bitprobe Model
• Dynamic word problems
• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• scientific article; zbMATH DE number 7471669 (Why is no real title available?)
• Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
• On the cell probe complexity of dynamic membership
• Logarithmic Lower Bounds in the Cell-Probe Model
• Tight bounds for the partial-sums problem
• Automata, Languages and Programming
• Using hashing to solve the dictionary problem
• Lower bound framework for differentially private and oblivious data structures
• Dynamic membership for regular languages

This page was built for publication: On dynamic bit-probe complexity

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