New Lower Bound Techniques for Dynamic Partial Sums and Related Problems

DOI10.1137/S0097539701391592MaRDI QIDQ4706229zbMATH OpenFDO

Authors Thore Husfeldt, Theis Rauhe

Publication date 19 June 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539701391592

zbMATH Keywords

cell-probe modeldata structuredynamic algorithmpartial sum

Mathematics Subject Classification ID

Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower bounds for dynamic connectivity
• scientific article; zbMATH DE number 1476488
• The cell probe complexity of dynamic range counting
• On dynamic bit-probe complexity

Cited in

(18)

• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Dynamic nested brackets
• Compressed dynamic range majority and minority data structures
• On dynamic bit-probe complexity
• Upper and lower bounds on the power of advice
• Dynamic range majority data structures
• scientific article; zbMATH DE number 1002202 (Why is no real title available?)
• Orbital model for a class of algorithms solving the partial sums problem
• Lower bounds for dynamic connectivity
• On the Complexity of Maintaining Partial Sums
• scientific article; zbMATH DE number 1476488 (Why is no real title available?)
• Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
• Logarithmic Lower Bounds in the Cell-Probe Model
• Tight bounds for the partial-sums problem
• A little advice can be very helpful
• Partial sums on the ultra-wide word RAM
• A generalization of a lower bound technique due to Fredman and Saks
• Internal masked prefix sums and its connection to fully internal measurement queries

This page was built for publication: New Lower Bound Techniques for Dynamic Partial Sums and Related Problems

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