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\colon\{0,1\}^n\to[-1,1],$ we construct a polynomial $p_{robust}\colon\mathbf{R}^n\to\mathbf{R}$ of degree $O(\deg p+\log\frac1\epsilon)$ that $\epsilon$-approximates $p$ and is additionally robust to noise in the inputs: $|p(x)-p_{robust}(x+\delta)|<\epsilon$ for all $x\in\{0,1\}^n$ and all $\delta\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.