A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
Ronald de Wolf · Quantum Information and Computation · 2008
The degrees of polynomials representing or approximating Boolean functions are a prominent tool in various branches of complexity theory. Sherstov recently characterized the minimal degree $deg_{\eps}(f)$ among all polynomials (over $\mathbb{R}$) that approximate a symmetric function $f:\01^n\rightarrow\01$ up to worst-case error $\eps$: $ deg_{\eps}(f)=\widetilde{\Theta}\left(deg_{1/3}(f) + \sqrt{n\log(1/\eps)}\right).$ In this note we show how a tighter version (without the log-factors hidden in the $\widetilde{\Theta}$-notation), can be derived quite easily using the close connection between polynomials and quantum algorithms.