pdf icon
Making Polynomials Robust to Noise
Received: July 1, 2012
Revised: May 14, 2013
Published: June 11, 2013
Download article from ToC site:
[PDF (291K)] [PS (1104K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
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]

$ \newcommand{\R}{{\mathbb R}} \newcommand{\zoon}{\{0,1\}^n} \newcommand{\tildeg}{\,\deg\hspace{-18pt}\widetilde{\rule{0mm}{6pt}\hspace{18pt}}} \newcommand{\robust}{{\operatorname{robust}}} $

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.