数据流模型与判定树模型中的几个问题研究

关于问题难解性的研究是计算复杂性研究领域最核心的问题，证明强的复杂性下界长期以来一直是理论计算机科学领域、乃至数学领域具有挑战性的课题，亟待理论和方法的创新。本项目计划在数据流模型和判定树模型两方面探索证明强的复杂性下界的新方法。在数据流模型中，一个关键的科学问题是如何能够使用尽可能少的存储空间来完成海量数据的处理，我们计划研究最短路问题、最大子团问题等几个问题的最优空间复杂度下界，力争提出流模型下证明最优空间复杂度下界的新方法。在判定树模型中一个重要的科学问题是对sensitivity复杂度下界的刻画，我们计划研究关于图性质的Turan猜想等几个问题，发展证明sensitivity复杂度下界的新技术，揭示其与block sensitivity复杂度之间的内在联系。

关于问题难解性的研究是算法复杂性研究领域的核心问题，证明强的复杂性下界长期以来一直是理论计算机科学领域、乃至数学领域具有挑战性的课题。本项目从数据流模型和判定树模型两方面研究了证明强的复杂性下界的新方法。取得的主要进展包括：.在流式数据的研究方面，提出了从近似最大子团的两方通信复杂度问题到其流式算法空间复杂度的规约；引入Ramsey理论、Semeredi正则引理等极值图论中的数学工具；构造了从SET-DISJ问题到近似最大子团问题的规约，对近似最大子团问题证明了紧的通信复杂度下界和流式算法空间复杂度下界。针对流式模型下矩阵奇异性判定等问题，提出了使用函数的傅立叶变换系数作为对偶近似范数方法中所需使用的证据，证明了有限域上判定矩阵是否奇异等问题紧的通信复杂度下界和流式算法的空间复杂度下界。.在判定树复杂性的研究方面，借助超立方体的等周不等式、关于布尔函数的傅立叶变换等数学工具，改进了之前Kenyon和Kutin在04年证明的敏感度-块敏感度猜想上界，将上界从e^n下降到2^n，该上界也适用于比块敏感度更强的证书复杂度。研究了异或型判定树的计算能力，借助查询消去等技术，证明了在以牺牲一个平均敏感度复杂性因子为代价，可以将异或型判定树转化为一棵常规的判定树，并将此结果推广到更一般的线性判定树模型。.相关成果在ICALP, CRYPTO, STACS, AAAI, TAMC, ISAAC等国际会议和Design Codes and Cryptography, Theoretical Computer Science等学术期刊上发表，共发表论文25篇，相关工作得到了国际同行的关注和引用。