Randomized query complexity can beat certificate complexity

A long-standing open question in query complexity asks whether a total Boolean function can have randomized query complexity much smaller than its certificate complexity. Ben-David and Kothari construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also achieves Q(f) = O~(C(f)^{1/4}), nearly optimal for quantum query complexity.