A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
Abstract
Description
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 the reals) that approximate a symmetric function f:{0,1}^n-->{0,1} up to worst-case error \eps: deg_{\eps}(f) = ~Θ(deg_{1/3}(f) + \sqrt{n\log(1/\eps)}). In this note we show how a tighter version (without the log-factors hidden in the ~Θ-notation), can be derived quite easily using the close connection between polynomials and quantum algorithms.
7 pages LaTeX. 2nd version: corrected a few small inaccuracies
7 pages LaTeX. 2nd version: corrected a few small inaccuracies