By Alexander A. Sherstov | published 2012-05-19 |
1 |
Share:
Report a problem
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:{0,1}n->[-1,1], we construct a polynomial probust:Rn->R of degree O(deg p+log(1/ε)) that epsilon-approximates p and is robust to noise in the inputs: |p(x)-probust(x+δ)|<ε for all x∈ 0,1}n and all delta∈[-1/3,1/3]n.
Log in
|
Share:
