The Complexity of Dynamic Data Structures

点击翻译按钮获取中文摘要

Dynamic data storage and retrieval problems involve the representation of data in memory in such a way as to permit certain types of modifications of the data (updates) and question about the data (queries). The theory of data structures is concerned with finding such representations that are efficient with respect to various criteria, such as time per operation and memory required. On the other hand it is important to understand the intrinsic limitations of efficiency for any implementation. In the project, various data structure problems are analyzed: dynamic dictionary, orthogonal range queries and union-find with the aim of proving lower bounds on their complexities in the powerful cell-probe model of computation. The effect of register size on complexity and the relation between amortized and single operation complexity are being studied. Other topics outside of data structure theory are also being investigated, including: the power of bounded depth threshold circuits and some algorithmic problems in distributed computing.