Cell-probe lower bounds for succinct partial sums

No abstract is available for this paper.

• Publication year

  2010

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2010-01-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973075.11
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Two conditions for reducing the maximal length of node-disjoint paths in hypercubes

  2012cited by this paper
• Bit-probe lower bounds for succinct data structures

  2009cited by this paper
• Cell-Probe Lower Bounds for Prefix Sums

  2009cited by this paper
• Cell probe lower bounds for succinct data structures

  2009cited by this paper
• On the Redundancy of Succinct Data Structures

  2008cited by this paper
• Randomization does not help searching predecessors

  2007cited by this paper
• On the Size of Succinct Indices

  2007cited by this paper
• Time-space trade-offs for predecessor search

  2006cited by this paper
• Optimal lower bounds for rank and select indexes

  2006cited by this paper
• Lower bounds on the size of selection and rank indexes

  2005cited by this paper
• The cell probe complexity of succinct data structures

  2003cited by this paper
• Low Redundancy in Static Dictionaries with Constant Query Time

  2002cited by this paper
• Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

  2002cited by this paper
• 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)

  2002cited by this paper
• A novel autosomal dominant distal myopathy with early respiratory failure

  2001cited by this paper
• Cell probe complexity-a survey

  1999cited by this paper
• Space Efficient Suffix Trees

  1998cited by this paper
• Efficient suffix trees on secondary storage

  1996cited by this paper
• Space-efficient static trees and graphs

  1989cited by this paper

• Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck

  2025cites this paper
• Time/Space Tradeoffs for Generic Attacks on Delay Functions

  2025cites this paper
• Optimal Static Fully Indexable Dictionaries

  2025cites this paper
• Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations

  2025cites this paper
• Optimal Static Dictionary with Worst-Case Constant Query Time

  2024cites this paper
• Access-Redundancy Tradeoffs in Quantized Linear Computations

  2024cites this paper
• Access-Redundancy Tradeoffs in Quantized Linear Computations

  2023cites this paper
• New Sampling Lower Bounds via the Separator

  2023cites this paper
• A Learned Approach to Design Compressed Rank/Select Data Structures

  2022cites this paper
• Adaptive Succinctness

  2021cites this paper
• Nearly Tight Lower Bounds for Succinct Range Minimum Query

  2021cites this paper
• Lower bounds for samplers and data structures via the cell-probe separator

  2021cites this paper
• A "Learned" Approach to Quicken and Compress Rank/Select Dictionaries

  2021cites this paper
• Lower bound for succinct range minimum query

  2020influential citation
• Predecessor Search

  2020cites this paper
• Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long

  2020cites this paper
• Faster Dynamic Range Mode

  2020cites this paper
• Sampling lower bounds: boolean average-case and permutations

  2020cites this paper
• Nearly optimal static Las Vegas succinct dictionary

  2019cites this paper
• Towards an Exponential Lower Bound for Secret Sharing

  2019cites this paper
• Exponential Lower Bounds for Secret Sharing

  2019cites this paper
• How to Store a Random Walk

  2019cites this paper
• Improved Time and Space Bounds for Dynamic Range Mode

  2018cites this paper
• Optimal Substring Equality Queries with Applications to Sparse Text Indexing

  2018cites this paper
• Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs

  2018cites this paper
• Local decodability of the Burrows-Wheeler transform

  2018cites this paper
• Optimal succinct rank data structure via approximate nonnegative tensor decomposition

  2018influential citation
• A sampling lower bound for permutations

  2017cites this paper
• Tight cell probe bounds for succinct Boolean matrix-vector multiplication

  2017cites this paper
• Compressed bit vectors based on variable-to-fixed encodings

  2016cites this paper
• Rank and Select Operations on Binary Strings

  2016cites this paper
• Sampling from Discrete Distributions and Computing Frechet Distances

  2015cites this paper
• Statistical and repetition-based compressed data structures

  2015cites this paper
• Compressed Bit Vectors Based on Variable-to-Fixed Encodings

  2014cites this paper
• Adjacency Labeling Schemes and Induced-Universal Graphs

  2014cites this paper
• Space-Efficient Data Structures in the Word-RAM and Bitprobe Models

  2013cites this paper
• Succinct sampling from discrete distributions

  2013cites this paper
• Dynamic Compressed Strings with Random Access

  2013cites this paper
• Random Access to High-Order Entropy Compressed Text

  2013cites this paper
• Mihai Pǎtraşcu: obituary and open problems

  2013cites this paper
• Wavelet trees for all

  2012cites this paper
• Advanced rank/select data structures: succinctness, bounds and applications

  2012cites this paper
• Succinct representations of permutations and functions

  2011cites this paper
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index

  2011cites this paper
• Optimal Lower and Upper Bounds for Representing Sequences

  2011cites this paper
• New Lower and Upper Bounds for Representing Sequences

  2011cites this paper
• Optimal Indexes for Sparse Bit Vectors

  2011cites this paper
• The Complexity of Distributions

  2010cites this paper
• Some Communication Complexity Results and their Applications

  2010cites this paper
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model

  2010cites this paper
• An Alternative to Arithmetic Coding with Local Decodability

  2010cites this paper
• Entropy-bounded representation of point grids

  2010cites this paper
• Changing base without losing space

  2010cites this paper
• Fully Functional Static and Dynamic Succinct Trees

  2009cites this paper
• Bit-probe lower bounds for succinct data structures

  2009cites this paper
• Fully compressed suffix trees

  2008cites this paper