Advanced

New lower bound techniques for dynamic partial sums and related problems

Husfeldt, Thore LU and Rauhe, Theis (2003) In SIAM Journal on Computing 32(3). p.736-753
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
cell-probe model, data structure, partial sum, dynamic algorithm
in
SIAM Journal on Computing
volume
32
issue
3
pages
736 - 753
publisher
SIAM Publications
external identifiers
  • wos:000183459000010
  • scopus:0038638395
ISSN
0097-5397
DOI
10.1137/S0097539701391592
language
English
LU publication?
yes
id
51d7749d-bbc3-4027-a749-d3eb25c4f70a (old id 308353)
date added to LUP
2007-09-13 12:19:38
date last changed
2018-01-07 08:54:01
@article{51d7749d-bbc3-4027-a749-d3eb25c4f70a,
  abstract     = {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.},
  author       = {Husfeldt, Thore and Rauhe, Theis},
  issn         = {0097-5397},
  keyword      = {cell-probe model,data structure,partial sum,dynamic algorithm},
  language     = {eng},
  number       = {3},
  pages        = {736--753},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {New lower bound techniques for dynamic partial sums and related problems},
  url          = {http://dx.doi.org/10.1137/S0097539701391592},
  volume       = {32},
  year         = {2003},
}