Learning low-degree functions from a logarithmic number of random queries

We prove that for any integer n N, d {1,...,n} and any ε,δ (0,1), a bounded function f: { 1,1} We say that f has degree at most d {1,...,n} if ˆ f (S) 0 for every subset S with S d. 1.1. R which is a good approximation of f up to a given error in some prescribed metric.