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.