10
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Artem Kaznatcheev ♦
    Mar 28, 2011 at 22:35
  • $\begingroup$ OK, I agree. So the relaxation argument seems really only to apply to the step from C(f) to ADV(f). Anyway, I think slide 40 I was refering to above nicely summarizes the generalization steps taken from C(f) via a relaxation to ADV(f) and then via another generalization to ADV±(f), which is the connection between C(f) and ADV±(f) that you were asking about. $\endgroup$
    – Martin Schwarz
    Mar 29, 2011 at 5:50
  • $\begingroup$ Thanks for the answer. This kind of connection goes directly through query complexity and relates to a previous question, but I think I am trying to look for more direct connections through span programs. In particular I am trying to gain more insight into span programs themselves without using my knowledge of quantum query complexity. I will edit my question to make that more clear and see if it generates any further insights into span programs. $\endgroup$
    – Artem Kaznatcheev ♦
    Mar 29, 2011 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.