2026-10-03T02:59:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8495 2024-03-06T09:42:16Z ddc:004 open_access

All Classical Adversary Methods are Equivalent for Total Functions Ambainis, Andris Kokainis, Martins Prusis, Krisjanis Vihrovs, Jevgenijs Randomized Query Complexity Lower Bounds Adversary Bounds Fractional Block Sensitivity 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. For partial functions, we show unbounded separations between fbs(f) and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than sqrt(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) = Omega(sqrt(n * bs(f))). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andris Ambainis and Martins Kokainis and Krisjanis Prusis and Jevgenijs Vihrovs 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.8 urn:nbn:de:0030-drops-84953 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.8 eng https://creativecommons.org/licenses/by/3.0/legalcode