You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
Scinawa
changed the title
Extend the discussion on the Adversary bound (Chapter 14)
Chapter 14 - TODO
Oct 1, 2022
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.
The text was updated successfully, but these errors were encountered: