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

We prove that every bounded function f:−1,1n→[−1,1] of degree at most d can be learned with L2-accuracy ε and confidence 1−δ from log(n/δ) ε−d−1 Cd3/2√logd random queries, where C>1 is a universal finite constant.