New lower bound techniques for dynamic partial sums and related problems
(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:
https://lup.lub.lu.se/record/308353
- author
- Husfeldt, Thore LU and Rauhe, Theis
- organization
- publishing date
- 2003
- 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
- Society for Industrial and Applied Mathematics
- 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
- 2016-04-01 15:55:49
- date last changed
- 2022-02-05 03:59:09
@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}},
keywords = {{cell-probe model; data structure; partial sum; dynamic algorithm}},
language = {{eng}},
number = {{3}},
pages = {{736--753}},
publisher = {{Society for Industrial and Applied Mathematics}},
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}},
doi = {{10.1137/S0097539701391592}},
volume = {{32}},
year = {{2003}},
}