A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
| dc.creator | de Wolf, Ronald | |
| dc.date | 2008-02-13 | |
| dc.date | 2008-02-15 | |
| dc.date.accessioned | 2026-07-07T09:20:43Z | |
| dc.date.available | 2026-07-07T09:20:43Z | |
| dc.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. | |
| dc.description | 7 pages LaTeX. 2nd version: corrected a few small inaccuracies | |
| dc.identifier | https://arxiv.org/abs/0802.1816 | |
| dc.identifier | http://arxiv.org/abs/0802.1816 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/154807 | |
| dc.subject | Quantum Physics | |
| dc.title | A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions | |
| dc.type | text |