The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Robust polynomials and quantum algorithms

Buhrman, H (CWI)
Tuesday 24 August 2004, 09:20-10:10

Seminar Room 1, Newton Institute


We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We show that, in contrast to the classical model of Feige et. al., every Boolean function can be computed by O(n) quantum queries even in the model with noise. This implies, for instance, the somewhat surprising result that every Boolean function has robust degree bounded by O(n).

This joint work with Ilan Newman, Hein Roehrig, and Ronald de Wolf


MP3MP3 Real AudioReal Audio

Back to top ∧