Randomized query complexity can beat certificate complexity

We resolve a long-standing question in query complexity about whether a randomized algorithm can solve a problem faster than its certificate complexity, i.e., faster than the size of the smallest witness for the function. We then generalize this to show a stronger separation between quantum algorithms and certificate complexity.