Random low-degree polynomials are hard to approximate
Random low-degree polynomials are hard to approximate
复制标题
DOI：
10.1007/s00037-011-0020-6
复制
发表时间：
2009-08
影响因子：
1.4
通讯作者：
Ido Ben-Eliezer;Rani Hod;Shachar Lovett
中科院分区：
文献类型：
--
作者：
Ido Ben-Eliezer;Rani Hod;Shachar Lovett
我们研究了一个典型的多元多项式可以近似低次多项式的问题。我们证明了几乎所有的次数多项式与所有次数至多为d − 1的多项式只有指数小的相关性，对于所有的degreesup到Θ（n）。也就是说，一个随机次数的多项式不允许较低次数的良好近似.为了证明这一点，我们证明了一个随机低次多项式的偏差分布的远尾估计。最近，关于Reed-Muller码的重量分布得到了一些结果。我们的结果可以解释为一个新的大偏差界的重量分布的Reed-Muller码。
We study the problem of how well a typical multivariate polynomial can be approximated by lower-degree polynomials over. We prove that almost all degreedpolynomials have only an exponentially small correlation with all polynomials of degree at mostd− 1, for all degreesdup to Θ(n). That is, a random degreedpolynomial does not admit a good approximation of lower degree. In order to prove this, we prove far tail estimates on the distribution of the bias of a random low-degree polynomial. Recently, several results regarding the weight distribution of Reed–Muller codes were obtained. Our results can be interpreted as a new large deviation bound on the weight distribution of Reed–Muller codes.