Making polynomials robust to noise
Making polynomials robust to noise
复制标题
使多项式对噪声具有鲁棒性
DOI：
10.1145/2213977.2214044
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov
任何计算模型中的一个基本问题是，当输入或中间计算受到恒定速率的噪声影响时，如何可靠地计算给定函数。理想情况下，与无噪声情况相比，人们最多希望使用更多恒定因子的资源。这个问题已经针对决策树、电路、自动机、数据结构、广播网络、通信协议和其他模型进行了研究。
布尔曼等人。 (2003) 提出了实多项式的噪声计算问题。我们针对这个问题给出了完整的解决方案。对于任何多项式 p:{0,1}n->[-1,1]，我们构造一个 O(deg p+log(1/ε)) 度的多项式 probust:Rn->R，它 epsilon 近似 p 并且对输入中的噪声具有鲁棒性：|p(x)-probust(x+δ)|n 和所有 deltaε[-1/3,1/3]n。该结果对于所有参数来说都是最佳的。我们为每个 p 显式构造 probust。以前，甚至对于 p=x1 ⊕ x2 ⊕ ... ⊕ xn 也可以给出这样的构造（Buhrman et al., 2003）。该证明提供了一种独立感兴趣的技术，它允许人们强制部分消除多项式中的误差项。
A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has been studied for decision trees, circuits, automata, data structures, broadcast networks, communication protocols, and other models.
Buhrman et al. (2003) posed the noisy computation problem for real polynomials. We give a complete solution to this problem. For any polynomial p:{0,1}n->[-1,1], we construct a polynomial probust:Rn->R of degree O(deg p+log(1/ε)) that epsilon-approximates p and is robust to noise in the inputs: |p(x)-probust(x+δ)|n and all delta∈[-1/3,1/3]n. This result is optimal with respect to all parameters. We construct probust explicitly for each p. Previously, it was open to give such a construction even for p=x1 ⊕ x2 ⊕ ... ⊕ xn (Buhrman et al., 2003). The proof contributes a technique of independent interest, which allows one to force partial cancellation of error terms in a polynomial.