Revised: May 14, 2013
Published: June 11, 2013
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.