Paper Info
Title
Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method
Abstract
We introduce new models for dynamic computation based on the cell probe model of Fredman and Yao. We give these models access to nondeterministic queries or the right answer 1 as an oracle. We prove that for the dynamic partial sum problem, these new powers do not help, the problem retains its lower bound of (logn= log log n). From these results we easily derive a large number of lower bounds of order (logn= log log n) for conventional dynamic models like the random ac- cess machine. We prove lower bounds for dynamic algorithms for reachability in directed graphs, planarity testing, planar point location, incremental pars- ing, fundamental data structure problems like maintaining the majority of the prexes of a string of bits and range queries. We characterise the complexity of maintaining the value of any symmetric function on the prexes of a bit string.
Year
DOI
Venue
1998
10.1007/BFb0055041
ICALP
Keywords
Field
DocType
dynamic problems,hardness results,chronogram method,symmetric function,directed graph,partial sums,range query,lower bound,point location,data structure
Discrete mathematics,Binary logarithm,Combinatorics,Nondeterministic algorithm,Upper and lower bounds,Range query (data structures),Oracle,Lattice graph,Dynamic problem,Mathematics,Cell-probe model,Distributed computing
Conference
Volume
ISSN
ISBN
1443
0302-9743
3-540-64781-3
Citations 
PageRank 
References 
9
0.68
26
Authors
2
Name
Order
Citations
PageRank
Thore Husfeldt173340.87
Theis Rauhe266135.11