Revised: May 14, 2013

Published: June 11, 2013

**Keywords:**computation with noise, polynomial approximation, robust polynomials, real polynomials on the Boolean hypercube

**Categories:**noisy computation, polynomials - multivariate, approximation, Boolean functions, special issue, Boolean special issue

**ACM Classification:**F.0, F.1.3

**AMS Classification:**68Q05, 68Q87

**Abstract:**
[Plain Text Version]

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ö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\colon\zoon\to[-1,1],$ we construct a corresponding
polynomial $p_\robust\colon\R^n\to\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\zoon$ 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--758, 2012.