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

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

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.