Theory of Computing
-------------------
Title : Making Polynomials Robust to Noise
Authors : Alexander A. Sherstov
Volume : 9
Number : 18
Pages : 593-615
URL : http://www.theoryofcomputing.org/articles/v009a018
Abstract
--------
A basic question in any model of computation is how to reliably
compute a given function when its inputs are subject to noise.
Buhrman, Newman, R{\"o}hrig, and de Wolf (2003) posed the noisy
computation problem for _real polynomials_. We give a complete
solution to this problem. For any $\delta>0$ and any polynomial
p : {0,1}^n --> [-1,1], we construct a corresponding polynomial
p_{robust} : R^n --> R of degree O(\deg p+\log1/\delta) that is
robust to noise in the inputs: |p(x)-p_{robust}(x+\epsilon)|<\delta
for all x\in {0,1}^n and all \epsilon\in[-1/3,1/3]^n. This result is
optimal with respect to all parameters. We construct p_{robust}
explicitly for each p. Previously, it was open to give such a
construction even for p=x_1\oplus x_2\oplus \cdots\oplus x_n
(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.
An extended abstract of this article appeared in the Proceedings of
the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC'12),
pages 747--757, 2012.