Learning low-degree functions from a logarithmic number of random
  queries
  We prove that every bounded function $f:\{-1,1\}^n\to[-1,1]$ of degree at
most $d$ can be learned with $L_2$-accuracy $\varepsilon$ and confidence
$1-\delta$ from $\log(\tfrac{n}{\delta})\,\varepsilon^{-d-1}
C^{d^{3/2}\sqrt{\log d}}$ random queries, where $C>1$ is a universal finite
constant.
