The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

New lower bound techniques for dynamic partial sums and related problems

På svenska

Author

Summary, in English

We study the complexity of the dynamic partial sum problem in the cell-probe model. We give the model access to nondeterministic queries and prove that the problem remains hard. We give the model access to the right answer +/-1 as an oracle and prove that the problem remains hard. This suggests which kind of information is hard to maintain. From these results, we derive a number of lower bounds for dynamic algorithms and data structures: We prove lower bounds for dynamic algorithms for existential range queries, reachability in directed graphs, planarity testing, planar point location, incremental parsing, and fundamental data structure problems like maintaining the majority of the prefixes of a string of bits. We prove a lower bound for reachability in grid graphs in terms of the graph's width. We characterize the complexity of maintaining the value of any symmetric function on the prefixes of a bit string.

Department/s

  • Computer Science

Publishing year

2003

Language

English

Pages

736-753

Publication/Series

SIAM Journal on Computing

Volume

32

Issue

3

Document type

Journal article

Publisher

Society for Industrial and Applied Mathematics

Topic

  • Computer Science

Keywords

  • cell-probe model
  • data structure
  • partial sum
  • dynamic algorithm

Status

Published

ISBN/ISSN/Other

  • ISSN: 0097-5397