Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Chapter 14 - TODO #83

Open
Ikiga1 opened this issue Sep 20, 2022 · 0 comments
Open

Chapter 14 - TODO #83

Ikiga1 opened this issue Sep 20, 2022 · 0 comments

Comments

@Ikiga1
Copy link
Contributor

Ikiga1 commented Sep 20, 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.

@Scinawa Scinawa changed the title Extend the discussion on the Adversary bound (Chapter 14) Chapter 14 - TODO Oct 1, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant