Using the extra power of the negative adversary method

Question

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 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, ACL2011), 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 and GKNR2009). Why is so hard to use the negative adversary method to prove $\Omega(f(n))$ lower bounds on them?

Answer 1

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.