Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method

Thore Husfeldt
Theis Rauhe

November 1997

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 tex2html_wrap_inline22.

From these results we easily derive a large number of lower bounds of order tex2html_wrap_inline22 for conventional dynamic models like the random access machine. We prove lower bounds for dynamic algorithms for reachability in directed graphs, planarity testing, planar point location, incremental parsing, fundamental data structure problems like maintaining the majority of the prefixes of a string of bits and range queries. We characterise the complexity of maintaining the value of any symmetric function on the prefixes of a bit string

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.