Span programs, witness size, and certificate complexity
The minimum witness size over all witnesses of a span program for a given function equals the generalized adversary bound, as shown e.g. in Theorem 1.7 here. Further, the generalized adversary bound is just a semi-definite relaxation of certificate complexity, see e.g. slide 40 in Reichardt's tutorial. The relation to deterministic and randomized query complexity is discussed in these tutorial slides as well.