On Improved Degree Lower Bounds for Polynomial Approximation
On Improved Degree Lower Bounds for Polynomial Approximation
复制标题
关于多项式逼近的改进次数下界
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Srinivasan
中科院分区：
文献类型：
--
作者：
S. Srinivasan
f [x_1，...，x_n]中的多项式p被说对epsilon-approximate a
布尔函数f：{0,1}^n-> {0,1}在{0,1}^n上的分布d下
如果是根据分布D选择的随机X，则概率
P（X）不等于F（x），最多是Epsilon。 Smolensky（1987）
表明，对于任何恒定不同的素数P和Q，任何多项式P
在f_p [x_1，...，x_n]中（1/2q -Omega（1）） - 近似Boolean
函数mod_q：{0,1}^n-> {0,1} - 接受其输入iff
数量是非零模型Q-在均匀分布下
必须具有欧米茄学位（N^{1/2}）。
我们考虑找到明确功能的问题
f：{0,1}^n-> {0,1}
在 *某个分发 *下，程度小于N^{1/2 + Omega（1）}，用于
一些恒定的Epsilon> 0。我们在此显示了许多负面结果
方向：具体来说，我们证明了许多有趣的类
功能包括对称函数和线性阈值功能
在下面具有o（n^{1/2+o（1）}）的近似多项式
每个分布。这证明了这种模型的力量
计算。
反过来，以上结果为较低的结果提供了进一步的动力
有限的问题。使用上面获得的上限，我们表明
找到这样的函数F将具有以下应用：
ac^0 o f，其中f是对称和阈值门的类别；
通过ACC^0 [P]电路进行1轮压缩的下限；
与低度多项式相关的相关性下限改善了；和
（在进一步的条件下）表明内部产品（超过f_2）
功能没有小的AC^0 o mod_2电路。
A polynomial P in F[X_1,...,X_n] is said to epsilon-approximate a
boolean function F:{0,1}^n -> {0,1} under distribution D over {0,1}^n
if for a random x chosen according to distribution D, the probability
that P(x) is not equal to F(x) is at most epsilon. Smolensky (1987)
showed that for any constant distinct primes p and q, any polynomial P
in F_p[x_1,...,x_n] that (1/2q - Omega(1))-approximates the boolean
function MOD_q:{0,1}^n->{0,1} -- which accepts its input iff the
number of ones is non-zero modulo q -- under the uniform distribution
must have degree Omega(n^{1/2}).
We consider the problem of finding an explicit function
f:{0,1}^n->{0,1} that has no epsilon-approximating polynomial of
degree less than n^{1/2 + Omega(1)} under *some distribution*, for
some constant epsilon>0. We show a number of negative results in this
direction: specifically, we show that many interesting classes of
functions including symmetric functions and linear threshold functions
do have approximating polynomials of degree O(n^{1/2+o(1)}) under
every distribution. This demonstrates the power of this model of
computation.
The above results, in turn, provide further motivation for this lower
bound question. Using the upper bounds obtained above, we show that
finding such a function f would have applications to: lower bounds for
AC^0 o F where F is the class of symmetric and threshold gates;
stronger lower bounds for 1-round compression by ACC^0[p] circuits;
improved correlation lower bounds against low degree polynomials; and
(under further conditions) showing that the Inner Product (over F_2)
function does not have small AC^0 o MOD_2 circuits.