基于多项式插值法的近似计数算法研究

The study of the approximability of counting problems is an important topic in theoretical computer science. In recent ten years, close connections between approximate counting and other areas including statistical physics, combinatorics have been discovered. The polynomial interpolation approach plays a key role in these connections, it relates the approximability of a polynomial with the locations of its zeros in the complex plane. Moreover, it can also serve as a new algorithm design tool and many new approximate algorithms have been discovered based on it recently. In this proposal, I am going to further develop the approach and try to understand its connections with other classic algorithm design technique including Markov chain Monte Carlo method and the correlation decay method. The main purpose of the project is to design new approximation algorithms for some important counting problems including Holant problems and k-coloring.

对于计数问题的近似算法研究是理论计算机科学的重要方向之一。在过去的十年中，这一领域一直在蓬勃的发展，并逐渐展示了与统计物理、组合数学等其它基础学科间深刻的联系。其中，多项式插值法对于理解这些联系起到了重要的作用：它揭示了多项式的可近似性与其零点在复平面上分布位置的关系。并且，人们利用这种关系设计出了许多最新的近似算法。本项目致力于进一步发展和深化这一套技术，尝试揭示其与经典的近似计数算法设计方法，如马尔可夫链蒙特卡洛、相关性衰减等的联系。本项目的目标是通过发展这一技术，对一些重要的计数问题包括Holant问题、K-着色问题等给出新的近似算法。

近似计数是理论计算机科学的重要研究方向，本项目对该领域的重要问题和方法进行了研究和发展。主要成果包括：..- 第一个在Lovász local lemma条件下CNF可行解近线性时间的近似计数与采样算法；.- 新的图合法着色的近似计数和采样算法；.- 第一个超图独立集的完美采样器；.- 对于非对称的Holant问题在三度图上可近似性的部分分类结果。