数据结构的验证复杂性下界研究

数据结构是计算机科学的基础内容之一。数据机构复杂性理论探讨的是对数据的有效表示可以优化何种类型的计算，这个深刻的理论话题对于人类对计算本质的理解有着重大的理论意义。另一方面，在现实应用中，人们期望解决的大量现实问题都是关于数据的某一类信息的查询，可以被抽象成为不同形式的数据结构问题，因此，数据结构复杂性理论的研究也具有相当的现实指导意义。现有的数据结构复杂性理论面临着理论工具单一、理论体系不完备、以及不能适应新体系结构发展需求的问题。本课题将通过对数据结构的验证复杂性的研究，为数据结构复杂性分析提供新的理论工具，完善关于非确定数据结构复杂性的理论体系，并针对新的计算机体系结构建立与之相适应的数据结构复杂性理论。

本项目取得了如下研究成果：（一）对数据结构下界的两大工具“丰富性引理”和“直和-丰富性引理”，证明了他们对于数据结构的验证复杂性仍然成立。从而将所有使用这两条引理证明的复杂性下界同时推广到更强的非确定模型中。并且对于最重要的数据结构问题之一——高维最近邻问题，得到了更高的复杂性下界。（二）对于并行体系结构，例如多核 CPU 或者MapReduce 模型中的数据结构，提出了并行数据结构的理论模型low-contention data structure，并系统的研究了负载均衡对并行数据结构的时间和空间复杂性的影响。（三）对于基于大数据上的计算所引发的新类型的算法问题——计数问题，发展了基于相关性衰减的理论工具，对于一系列根本的计数问题，包括：独立集、图着色、2元约束满足问题等，得到了目前最好的算法。..该项目的多篇论文发表于理论计算机科学的顶级会议SODA'12, SODA'13（2篇）, FOCS'13等。