随机与代数方法在算法与复杂性理论中应用研究

Computational theory serves as the backbone of Computer Science. It has developed many important methods and fundamental results, which have significant impacts to many other branches of computer science. Randomization plays a crucial role in the development of theoretical computer science. It has become a basic tool in the fields of computational complexity, algorithm design, cryptography, and machine learning. Another tool, algebrization, provides methods that transform local combinatorial properties into algebraic problems, and bring a global point of view for computational problems. Algebraic methods were seen as core technologies in some recent breakthroughs of theoretical computer science.. The PIs of this proposal have systemic publication records in the two methods, and feel their importance to the fields of computational complexity, algorithm design, and machine learning. We plan to have a unified approach to study both randomization and algebrization methods, and apply them to problems in the borders of computational complexity, algorithm, and machine learning. We will explore how problems in the fields of complexity theory and algorithm design can be effectively solved utilizing randomization and algebrization, and will show how the two tools are crucial in several areas of theoretical Computer Science.

计算理论是计算机科学的基础，其发展的许多重要方法与结论，对计算机科学的各个分支的产生深远的影响。随机性方法在理论计算机科学的发展中起关键性作用，它已经成为计算复杂性理论、算法设计、密码学、机器学习等方向的核心工具。而代数方法是一种从整体角度来研究问题的方法，它通过将局部的组合性质代数化，从而把问题转化为代数问题来研究。最近，在理论计算机科学突破性成果的研究中，代数方法被当作是一种核心技术。. 本项目申请人在随机和代数方法的发展和应用上做出过系统性的工作，深感这两类方法在算法、复杂性理论和机器学习等领域的重要性。本项目中，我们将这两种方法综合起来进一步研究，并将其应用到计算复杂性、算法与机器学习领域交叉处的具体问题中，在此寻求更进一步的发展，希望能对计算机理论的本质问题有所推动，为应用领域中的难问题求解提供新的思路与方法。

在本基金的资助下，本项目围绕随机与代数方法在计算复杂性理论、算法设计和机器学习领域中的应用开展研究。取得的主要成果如下。在计算复杂性理论上，通过随机流模型在非确定时间复杂度类中研究稀疏集难度放大问题，提出一种有限域上的多项式代数方法证明了两个重要结论NEXP≠BPP和EXP≠ZPP。在算法方面，对集合并集问题，提出了一个将近线性有界轮数的随机近似算法，该算法在某种条件下其运行时间是亚线性的；为了更好地计算几何对象的体积和格点数目计数，我们引入了多面体电路的概念，设计了相应的算法计算几何对象的体积和计数几何区域的格点数目，这些方法可以应用连续多面体最大覆盖问题、多面体最大格点覆盖问题、多面体(1-β)格点集合覆盖问题、(1-β)连续多面体集合覆盖问题求解算法；对肾交换问题，我们构造了该问题的两个参数计算模型，并分别提出了基于随机划分技术和随机代数技术的随机参数算法；对l-伪森林问题，我们提出了一个线性时间的4l-近似算法；对近似森林删除问题，我们提出了一个运行时间O*(5^k4^l)的固定参数算法，改善了以前O*(5.0024^(k+l))算法；对旅行商问题，我们研究指数时间近似策略，提出了一个运行时间为O(1.66^n/ε)多项式空间的(1-ε)近似算法;对捐赠验证问题，我们提出了一个捐赠验证模型，并设计了一个随机算法来验证募集方面声称收到的金额是否是近似为捐赠者捐赠总额的(1-ε)。此外，基于研究成果，我们对机器学习和智能计算中的一些问题进行研究，把相关技术应用于图形图像处理等相关领域。本项目的研究，加深了我们对随机与代数方法的理解，为相关领域的难解问题求解提供了新的思路与方法。