<p>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 <a href="http://eccc.hpi-web.de/report/2010/110/" rel="nofollow">here</a>. Further, the <del>generalized</del> adversary bound is just a semi-definite relaxation of certificate complexity, see e.g. slide 40 in <a href="http://qip2011.quantumlah.org/images/QIPtutorial3.pdf" rel="nofollow">Reichardt's tutorial</a>. The relation to deterministic and randomized query complexity is discussed in these tutorial slides as well.</p>

CC BY-SA 2.5
2011-03-28T22:35:15.190Z
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](http://arxiv.org/PS_cache/quant-ph/pdf/0611/0611054v2.pdf) (pg. 25) is given a function $f$ with $C(f) = 3$ and $ADV^{\pm}(f) = 2 + 3\sqrt{5}/5 > 3$.
Artem Kaznatcheev
CC BY-SA 2.5
2011-03-29T05:50:32.177Z
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.
Martin Schwarz
CC BY-SA 2.5
2011-03-29T06:09:17.893Z
Thanks for the answer. This kind of connection goes directly through query complexity and relates to a [previous question](http://cstheory.stackexchange.com/questions/5359/quantum-query-complexity-and-certificate-complexity), 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.
Artem Kaznatcheev
CC BY-SA 2.5
2011-03-28T20:41:35.597Z
2011-03-29T05:52:01.677Z
2011-03-29T05:52:01.677Z
Martin Schwarz
<p>A span program is a linear-algebraic way of specifying a boolean function introduced <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=336536&amp;tag=1" rel="nofollow">here</a>. Recently, this model was <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2009.55" rel="nofollow">used</a> to show that the negative adversary method provides a tight characterization (at least up to $\log n/ \log \log n$) of quantum query complexity.</p>

<p>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?</p>

<p>EDIT (after an answer by Martin Schwarz): </p>

<p>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?</p>

<cc.complexity-theory><reference-request><quantum-computing><query-complexity>
Span programs, witness size, and certificate complexity
Artem Kaznatcheev
# Span programs, witness size, and certificate complexity

(Asked by: username_0 on 2011-03-28)

A span program is a linear-algebraic way of specifying a boolean function introduced [here](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=336536&tag=1). Recently, this model was [used](http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2009.55) 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 username_1):

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?

**Tags:** cc.complexity-theory, reference-request, quantum-computing, query-complexity


---

## 1 answers

### Answer by username_1 on 2011-03-28. Score: 5

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](http://eccc.hpi-web.de/report/2010/110/). Further, the ~~generalized~~ adversary bound is just a semi-definite relaxation of certificate complexity, see e.g. slide 40 in [Reichardt's tutorial](http://qip2011.quantumlah.org/images/QIPtutorial3.pdf). The relation to deterministic and randomized query complexity is discussed in these tutorial slides as well.

> **Comments:**
> **username_0**: 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](http://arxiv.org/PS_cache/quant-ph/pdf/0611/0611054v2.pdf) (pg. 25) is given a function $f$ with $C(f) = 3$ and $ADV^{\pm}(f) = 2 + 3\sqrt{5}/5 > 3$.  
> **username_1**: 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.  
> **username_0**: Thanks for the answer. This kind of connection goes directly through query complexity and relates to a [previous question](http://cstheory.stackexchange.com/questions/5359/quantum-query-complexity-and-certificate-complexity), 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.  

---

