论文标题
使用泰勒定理进行近似计数：调查
Approximate counting using Taylor's theorem: a survey
论文作者
论文摘要
在本文中，我们考虑了某些与图形相关的众所周知的多项式，包括独立性多项式和色多项式。这些多项式在图中计算某些对象：在独立性多项式和适当的着色的情况下，在色度多项式的情况下是独立的。他们还具有解释作为统计物理学的分区功能。 （大约）计算这些类型的多项式的算法问题已有近50年的研究，尤其是使用马尔可夫链技术。大约八年前，Barvinok根据泰勒的定理设计了一种新的算法方法，用于计算某些矩阵的永久性，此后，该方法已应用于各种多项式。本文旨在对该方法进行温和的介绍以及对相关技术和结果的部分调查。
In this article we consider certain well-known polynomials associated with graphs including the independence polynomial and the chromatic polynomial. These polynomials count certain objects in graphs: independent sets in the case of the independence polynomial and proper colourings in the case of the chromatic polynomial. They also have interpretations as partition functions in statistical physics. The algorithmic problem of (approximately) computing these types of polynomials has been studied for close to 50 years, especially using Markov chain techniques. Around eight years ago, Barvinok devised a new algorithmic approach based on Taylor's theorem for computing the permanent of certain matrices, and the approach has been applied to various graph polynomials since then. This article is intended as a gentle introduction to the approach as well as a partial survey of associated techniques and results.
