Non-adaptive data structure bounds for dynamic predecessor

DOI10.4230/LIPICS.FSTTCS.2017.20MaRDI QIDQ5136312zbMATH OpenFDO

Authors Joseph Boninger, Joshua Brody, Owen Kephart

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2017.20

zbMATH Keywords

dynamic data structureslower boundsnon-adaptivitypredecessor search

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• scientific article; zbMATH DE number 6538681
• scientific article; zbMATH DE number 7250167
• Time-space trade-offs for predecessor search
• Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
• A lower bound for finding predecessors in Yao's cell probe model

Cites work

• Distributed computation in dynamic networks
• scientific article; zbMATH DE number 6381684 (Why is no real title available?)
• scientific article; zbMATH DE number 6538681 (Why is no real title available?)
• Should Tables Be Sorted?
• The cell probe complexity of dynamic range counting
• The complexity of data aggregation in directed networks
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• Time-space trade-offs for predecessor search
• Towards polynomial lower bounds for dynamic problems
• Upper and lower bounds on the power of advice

Cited in

(4)

• scientific article; zbMATH DE number 6538681 (Why is no real title available?)
• Predecessor queries in dynamic integer sets
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Optimal non-adaptive cell probe dictionaries and hashing

This page was built for publication: Non-adaptive data structure bounds for dynamic predecessor

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