Tight bounds for the partial-sums problem

MaRDI QIDQ5501238zbMATH OpenFDO

Authors Mihai Patrascu, Erik D. Demaine

Publication date 3 August 2015

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Recommendations

• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
• On the Complexity of Maintaining Partial Sums
• Cell-probe lower bounds for succinct partial sums
• On dynamic bit-probe complexity
• Logarithmic Lower Bounds in the Cell-Probe Model

Cited in

(24)

• Orthogonal range searching in linear and almost-linear space
• Tight rank lower bounds for the Sherali-Adams proof system
• Tight bounds on expected time to add correctly and add mostly correctly
• Lower bounds for dynamic data structures on algebraic RAMs
• An efficient algorithm for solving the partial sum query problem
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Multidimensional segment trees can do range updates in poly-logarithmic time
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Upper and lower bounds for dynamic data structures on strings
• Orbital model for a class of algorithms solving the partial sums problem
• On the Complexity of Maintaining Partial Sums
• Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums
• scientific article; zbMATH DE number 1873247 (Why is no real title available?)
• Tight bounds for blind search on the integers
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• A Logarithmic Bound for Solving Subset Sum with P Systems
• Partial sums on the ultra-wide word RAM
• Partial sums on the ultra-wide word RAM
• Sum of Squares Bounds for the Empty Integral Hull Problem
• Internal masked prefix sums and its connection to fully internal measurement queries
• The optimal all-partial-sums algorithm in commutative semigroups and its applications for image thresholding segmentation
• Lower bounds for semi-adaptive data structures via corruption
• Super-logarithmic lower bounds for dynamic graph problems
• Low-light trees, and tight lower bounds for Euclidean spanners

This page was built for publication: Tight bounds for the partial-sums problem

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