The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)
The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)
复制标题
电路复杂度中的多项式方法在算法设计中的应用（特邀报告）
DOI：
10.4230/lipics.fsttcs.2014.47
复制
发表时间：
2014
期刊：
影响因子：
1.1
通讯作者：
Richard Ryan Williams
中科院分区：
文献类型：
--
作者：
Richard Ryan Williams
在电路复杂性中，多项式方法是在受限设置中证明电路下界的通用方法。其中一个表明，由充分限制的电路计算的函数以某种方式与低复杂度多项式“相关”，其中复杂度可以通过多项式的次数或单项式的数量来测量。然后，限制低复杂度多项式的能力的结果被扩展到受限制的电路。
用这种方法证明的旧定理最近在计算理论中的基本问题的算法设计中找到了有趣的应用。本文综述了其中的一些应用，并给出了一些新的应用。
In circuit complexity, the polynomial method is a general approach to proving circuit lower bounds in restricted settings. One shows that functions computed by sufficiently restricted circuits are "correlated" in some way with a low-complexity polynomial, where complexity may be measured by the degree of the polynomial or the number of monomials. Then, results limiting the capabilities of low-complexity polynomials are extended to the restricted circuits.
Old theorems proved by this method have recently found interesting applications to the design of algorithms for basic problems in the theory of computing. This paper surveys some of these applications, and gives a few new ones.
在 STDk/3[k ;
DOI：
--
发表时间：
2008
期刊：
Discrete Mathematics 308
影响因子：
--
作者：
Y. Hiramine;C. Suetake;K. Akiyama C. Suetake
通讯作者：
K. Akiyama C. Suetake