Partial sums on the ultra-wide word RAM

DOI10.1016/j.tcs.2022.01.002OpenAlexW4205985011MaRDI QIDQ5918471

Frederik Rye Skjoldjensen, Inge Li Gørtz, Philip Bille

Publication date: 1 February 2022

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

Full work available at URL: https://arxiv.org/abs/1908.10159

zbMATH Keywords

partial sumsword-level parallelismultra-wide word RAM

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

On representing the degree sequences of sublogarithmic-degree Wheeler graphs

Uses Software

• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct data structures for searchable partial sums with optimal worst-case performance
• Inherent complexity trade-offs for range query problems
• Implicit data structures for fast search and update
• Lower bounds for dynamic data structures on algebraic RAMs
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Algorithms in the Ultra-Wide Word Model
• Radix Sorting with No Extra Space
• On the Complexity of Maintaining Partial Sums
• Simplified stable merging tasks
• Parallel Prefix Computation
• A Lower Bound on the Complexity of Orthogonal Range Queries
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• A fast on-line adaptive code
• Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums
• Dynamic word problems
• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
• Succinct Partial Sums and Fenwick Trees
• Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection
• Logarithmic Lower Bounds in the Cell-Probe Model
• Partial sums on the ultra-wide word RAM
• A generalization of a lower bound technique due to Fredman and Saks

This page was built for publication: Partial sums on the ultra-wide word RAM