Record Details

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

BRICS Report Series

View Archive Info
 
 
Field Value
 
Title Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method
 
Creator Husfeldt, Thore
Rauhe, Theis
 
Description 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  Omega(log n/log log n). From these results we easily derive a large number of lower bounds of order Omega(log n/log log n) 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.
 
Publisher Aarhus University
 
Date 1997-06-02
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
 
Format application/pdf
 
Identifier https://tidsskrift.dk/brics/article/view/18958
10.7146/brics.v4i32.18958
 
Source BRICS Report Series; No 32 (1997): RS-32 Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method
BRICS Report Series; Nr. 32 (1997): RS-32 Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method
1601-5355
0909-0878
 
Language eng
 
Relation https://tidsskrift.dk/brics/article/view/18958/16597