Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-037 | 10th April 2012 19:53

#### Making Polynomials Robust to Noise

TR12-037
Authors: Alexander A. Sherstov
Publication: 13th April 2012 03:30
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.