Theory of Computing
-------------------
Title     : Making Polynomials Robust to Noise
Authors   : Alexander A. Sherstov
Volume    : 9
Number    : 18
Pages     : 593-615
URL       : https://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.