On representations by low-degree polynomials
On representations by low-degree polynomials
复制标题
关于低次多项式的表示
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
R. Smolensky
中科院分区：
文献类型：
--
作者：
R. Smolensky
在本文的第一部分中，我们表明，布尔立方体b/ sub n/嵌入在投射空间p/ sup n/中的子集s可以通过由低分子定义的b/ sub n/ subs的子集近似 - 仅当S的Hilbert函数的值相对于S的大小而言足够小时，仅数量多项式。该特性的使用提供了一种简单而直接的技术，用于证明在大小的大小上的下限ACC [P/SUP R/]电路。在第二部分中，我们查看通过ACC [p/sup r/]电路计算许多输出函数的问题，并在只有在指数较小的任务中才能正确正确时举一个示例。<< etx >>
In the first part of the paper we show that a subset S of a boolean cube B/sub n/ embedded in the projective space P/sup n/ can be approximated by a subset of B/sub n/ defined by nonzeroes of a low-degree polynomial only if the values of the Hilbert function of S are sufficiently small relative to the size of S. The use of this property provides a simple and direct technique for proving lower bounds on the size of ACC[p/sup r/] circuits. In the second part we look at the problem of computing many-output function by ACC[p/sup r/] circuit and give an example when such a circuit can be correct only at exponentially small fraction of assignments.<<ETX>>