Making polynomials robust to noise

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.

Authors

• Alexander A. Sherstov

Keywords

• polynomial approximation
• computation with noise
• real polynomials on the boolean hypercube