<p>Apparently, I cannot comment so this will be an answer, even if it only a partial answer.</p>

<p>Element-distinctness has a lower bound of $\Omega(N^{2/3})$ and its certificate complexity is $\sqrt{N}$, so if one tries to prove it using the adversary method, he would need to use the adversary method with negative weights (which is optimal), or why not the Multiplicative adversary method.</p>

<p>Otherwise, the polynomial method is sometimes easier to use that the adversary methods since it suffices to prove the <strong>existence of polynomial</strong> whereas for the adversary method, you need to <strong>explicitly</strong> have a good adversary matrix, and compute its operator norm.</p>

CC BY-SA 3.0
2011-08-04T23:30:53.360Z
This specifically does not answer the question. We can use the tightness of the negative adversary method to know that some adversary matrix MUST exist for problems like element-distinctness (or if we want property testing, collision problem). But that is not really using the negative adversary method, it using the polynomial method. I guess if the question is not clear enough, I should refine it.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-04T21:48:19.060Z
2011-08-04T22:35:51.333Z
2011-08-04T22:35:51.333Z
Loïck
<p>The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that hindered the adversary method:</p>

<ol>
<li><p>The property testing barrier: if all 0-instances are $\epsilon$-far from all 1-instances then the adversary method cannot prove a lower bound better than $\Omega(1/\epsilon)$.</p></li>
<li><p>The certificate complexity barrier: if $C_b(f)$ is the certificate complexity of $b$-instances then the adversary method cannot prove a lower bound better than $\sqrt{C_0(f)C_1(f)}$ where</p></li>
</ol>

<p>In the original <a href="http://arxiv.org/PS_cache/quant-ph/pdf/0611/0611054v2.pdf" rel="nofollow">$ADV^\pm$ paper</a> the authors construct an example function for which their method overcomes both barriers. However, I have not see examples of any natural problems where this has yielded new lower bounds. </p>

<blockquote>
  <p>Can you provide any references where the negative adversary method was used to achieve a lower bound that the original method could not attain?</p>
</blockquote>

<p>The biggest interest for me, is in property testing. Currently there are very few lower bounds on property testing, in fact I only know two (<a href="http://arxiv.org/abs/1005.0523" rel="nofollow">CFMdW2010</a>, <a href="http://arxiv.org/abs/1012.3174" rel="nofollow">ACL2011</a>), that both use the polynomial method (the first by reduction from the collision problem which was originally lower bounded by polynomial method). We know that there are properties that require $\Theta(f(n))$ quantum queries to check, for any computable $f(n) \in O(n)$ (by combining the results in <a href="http://arxiv.org/abs/quant-ph/0201117" rel="nofollow">BNFR2002</a> and <a href="http://eccc.hpi-web.de/report/2008/097/" rel="nofollow">GKNR2009</a>). Why is so hard to use the negative adversary method to prove $\Omega(f(n))$ lower bounds on them?</p>

CC BY-SA 3.0
2011-07-14T15:39:58.760Z
In the property testing barrier, you probably mean $\Omega(1/\epsilon)$ rather than $\Omega(1/n)$.
Robin Kothari
CC BY-SA 3.0
2011-07-15T00:14:59.560Z
I know of an application of the negative adversary in cryptography by Brassard, Hoyer, Kalach, Kaplan, Laplante and Salvail (http://www.iacr.org/conferences/crypto2011/abstracts/385.htm) that will appear in CRYPTO'11. They used the composition theorem to prove a gap in Merkle games for a quantum adversary working against quantum parties interchanging a message. Sadly, the don't have a final version of the paper yet. So maybe you could wait for the proceedings or contact the authors.
Marcos Villagra
CC BY-SA 3.0
2011-08-12T01:33:52.907Z
the paper I mentioned in my comment above can be downloaded from arXiv (http://arxiv.org/abs/1108.2316). In particular, check lemma 1 and lemma 5 in the appendix.
Marcos Villagra
<cc.complexity-theory><reference-request><quantum-computing><query-complexity><property-testing>
Using the extra power of the negative adversary method
Artem Kaznatcheev
# Using the extra power of the negative adversary method

(Asked by: username_0 on 2011-07-14)

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that hindered the adversary method:

1. The property testing barrier: if all 0-instances are $\epsilon$-far from all 1-instances then the adversary method cannot prove a lower bound better than $\Omega(1/\epsilon)$.
2. The certificate complexity barrier: if $C\_b(f)$ is the certificate complexity of $b$-instances then the adversary method cannot prove a lower bound better than $\sqrt{C\_0(f)C\_1(f)}$ where

In the original [$ADV^\pm$ paper](http://arxiv.org/PS_cache/quant-ph/pdf/0611/0611054v2.pdf) the authors construct an example function for which their method overcomes both barriers. However, I have not see examples of any natural problems where this has yielded new lower bounds.

> Can you provide any references where the negative adversary method was used to achieve a lower bound that the original method could not attain?

The biggest interest for me, is in property testing. Currently there are very few lower bounds on property testing, in fact I only know two ([CFMdW2010](http://arxiv.org/abs/1005.0523), [ACL2011](http://arxiv.org/abs/1012.3174)), that both use the polynomial method (the first by reduction from the collision problem which was originally lower bounded by polynomial method). We know that there are properties that require $\Theta(f(n))$ quantum queries to check, for any computable $f(n) \in O(n)$ (by combining the results in [BNFR2002](http://arxiv.org/abs/quant-ph/0201117) and [GKNR2009](http://eccc.hpi-web.de/report/2008/097/)). Why is so hard to use the negative adversary method to prove $\Omega(f(n))$ lower bounds on them?

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

> **Comments:**
> **username_1**: In the property testing barrier, you probably mean $\Omega(1/\epsilon)$ rather than $\Omega(1/n)$.  
> **username_2**: I know of an application of the negative adversary in cryptography by Brassard, Hoyer, Kalach, Kaplan, Laplante and Salvail (http://www.iacr.org/conferences/crypto2011/abstracts/385.htm) that will appear in CRYPTO'11. They used the composition theorem to prove a gap in Merkle games for a quantum adversary working against quantum parties interchanging a message. Sadly, the don't have a final version of the paper yet. So maybe you could wait for the proceedings or contact the authors.  
> **username_2**: the paper I mentioned in my comment above can be downloaded from arXiv (http://arxiv.org/abs/1108.2316). In particular, check lemma 1 and lemma 5 in the appendix.  

---

## 1 answers

### Answer by username_3 on 2011-08-04. Score: 2

Apparently, I cannot comment so this will be an answer, even if it only a partial answer.

Element-distinctness has a lower bound of $\Omega(N^{2/3})$ and its certificate complexity is $\sqrt{N}$, so if one tries to prove it using the adversary method, he would need to use the adversary method with negative weights (which is optimal), or why not the Multiplicative adversary method.

Otherwise, the polynomial method is sometimes easier to use that the adversary methods since it suffices to prove the **existence of polynomial** whereas for the adversary method, you need to **explicitly** have a good adversary matrix, and compute its operator norm.

> **Comments:**
> **username_0**: This specifically does not answer the question. We can use the tightness of the negative adversary method to know that some adversary matrix MUST exist for problems like element-distinctness (or if we want property testing, collision problem). But that is not really using the negative adversary method, it using the polynomial method. I guess if the question is not clear enough, I should refine it.  

---

