# Span programs, witness size, and certificate complexity

A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (at least up to $\log n/ \log \log n$) of quantum query complexity.

The complexity measure connecting span programs to quantum query complexity is witness size. This measure seems rather similar to certificate complexity. Are there known connections between the two measures? What about the size (number of input vectors) measure for span programs and other measures like deterministic and randomized query complexity? What are the best known classical algorithms for evaluating span programs?

EDIT (after an answer by Martin Schwarz):

Of particular interest are conceptual connections that go directly through span programs as opposed to through the correspondence between witness size and quantum query complexity. Are there classical results that provide intuition about span programs/witness size and how they relate to deterministic and randomized query complexity?

• I can see that the (positive) adversary method is an SDP relaxation of certificate complexity, but I don't follow how the general (negative) adversary method is a relaxation of certificate complexity. As a counter-example, it seems that here (pg. 25) is given a function $f$ with $C(f) = 3$ and $ADV^{\pm}(f) = 2 + 3\sqrt{5}/5 > 3$. – Artem Kaznatcheev Mar 28 '11 at 22:35