Quantum query complexity and certificate complexity A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum size of a certificate for input $x$ and the certificate complexity $C(f) = \max_x C_x(f)$. Thus, certificate complexity can be seen as a form of query complexity for nondeterministic machines: guess the smallest certificate for $x$ and then verify with $C_x(f)$ many queries. This is used as an intermediate complexity measure when proving relationships between deterministic query complexity ($D(f)$) and quantum query complexity ($Q_2(f)$).

Is it known, or believed that for a total functions $f$, $C(f) \leq Q_2(f)$? Are there any total functions $f$, where it is know that $C(f) \in o(Q_2(f))$ (or vice-versa)? And just for fun: does this question correspond in some formal way to the questions associated NP vs. BQP?
In the paper Negative weights make adversaries stronger, Lee, Spalek, and Hoyer give a function for which $ADV^{&#177;}(f)= \Omega( ({C_0(f)C_1(f)})^{0.549})$, where $ADV^&#177;$ denotes the general adversary lower bound. This lower bound has since been proved to characterize quantum query complexity. 

This function is obtained by composing a function on a few bits bits with itself $d$ times. You get in the end $C_0(f)=C_1(f)=3^d$ and thus $C(f) \in o(Q_2(f))$.