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.