All Classical Adversary Methods Are Equivalent for Total Functions
| العنوان: | All Classical Adversary Methods Are Equivalent for Total Functions |
|---|---|
| المؤلفون: | Jevgēnijs Vihrovs, Andris Ambainis, Martins Kokainis, Krišjānis Prūsis, Aleksejs Zajakins |
| المصدر: | ACM Transactions on Computation Theory. 13:1-20 |
| بيانات النشر: | Association for Computing Machinery (ACM), 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | FOS: Computer and information sciences, Kolmogorov complexity, 010102 general mathematics, Block (permutation group theory), 0102 computer and information sciences, Function (mathematics), Computational Complexity (cs.CC), Adversary, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Combinatorics, Computer Science - Computational Complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, Partial function, Sensitivity (control systems), 0101 mathematics, Equivalence (measure theory), Mathematics |
| الوصف: | We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than √ n ⋅ bs( f ), where n is the number of variables and bs( f ) is the block sensitivity. Then, we exhibit a partial function f that matches this upper bound, fbs( f ) = Ω (√ n ⋅ bs( f )). |
| تدمد: | 1942-3462 1942-3454 |
| DOI: | 10.1145/3442357 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::34444b11ce488cbcfff186141a6fdea6 https://doi.org/10.1145/3442357 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....34444b11ce488cbcfff186141a6fdea6 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 19423462 19423454 |
|---|---|
| DOI: | 10.1145/3442357 |