On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation
On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation
复制标题
关于通过多项式插值枚举单项式和其他组合结构
DOI：
--
复制
发表时间：
2013
影响因子：
0.5
通讯作者：
Y. Strozecki
中科院分区：
文献类型：
--
作者：
Y. Strozecki
我们研究在枚举复杂性的背景下生成黑盒多项式的单项式的问题。我们提出了三种新的随机算法，用于具有多项式或增量延迟的受限多项式类别，以及与经典算法相同的全局运行时间。我们介绍 TotalBPP、IncBPP 和 DelayBPP，它们是枚举问题中最常见类别的概率对应项。我们的插值算法应用于几个组合枚举问题的代数表示，这些问题被证明属于所引入的复杂性类别。特别地，3-均匀超图的生成超树可以用多项式延迟来枚举。最后，我们研究了电路给出的多项式，并证明我们可以对有界深度电路类的插值算法进行去随机化。我们还证明了低次数和小电路复杂度的多项式上的一些问题的难度，这表明我们良好的多线性多项式插值算法不能推广到2次多项式。本文是 Strozecki（计算机科学数学基础，第 629-640 页，2010 年）和作者博士论文第三章的改进和扩展版本。论文（Strozecki，博士论文，2010 年）。
We study the problem of generating the monomials of a black box polynomial in the context of enumeration complexity. We present three new randomized algorithms for restricted classes of polynomials with a polynomial or incremental delay, and the same global running time as the classical ones. We introduce TotalBPP, IncBPP and DelayBPP, which are probabilistic counterparts of the most common classes for enumeration problems. Our interpolation algorithms are applied to algebraic representations of several combinatorial enumeration problems, which are so proved to belong to the introduced complexity classes. In particular, the spanning hypertrees of a 3-uniform hypergraph can be enumerated with a polynomial delay. Finally, we study polynomials given by circuits and prove that we can derandomize the interpolation algorithms on classes of bounded-depth circuits. We also prove the hardness of some problems on polynomials of low degree and small circuit complexity, which suggests that our good interpolation algorithm for multilinear polynomials cannot be generalized to degree 2 polynomials. This article is an improved and extended version of Strozecki (Mathematical Foundations of Computer Science, pp. 629–640, 2010) and of the third chapter of the author’s Ph.D. Thesis (Strozecki, Ph.D. Thesis, 2010).