Description
Extend the discussion on the Adversary bound
We should extend the chapter including a discussion about the weighted adversary bound. Moreover, it would be interesting to discuss the primal and the dual formulations of the bound and how we get both an upper bound and a lower bound.
Nice and compact presentation of some results from the adversary bound:
Ambainis, Andris, et al. "Efficient quantum algorithms for (gapped) group testing and junta testing." Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2016.
Other references:
P. Høyer, T. Lee, and R. Spalek. Negative weights make adversaries stronger. In Proc. of 39th ACM STOC, pages 526–535, 2007.
B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In Proc. of 50th IEEE FOCS, pages 544–551, 2009.