Title: All Classical Adversary Methods are Equivalent for Total Functions,
Abstract: 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 $\text{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 $\text{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 $\sqrt{n \cdot \text{bs}(f)}$, where $n$ is the
number of variables and $\text{bs}(f)$ is the block sensitivity. Then we
exhibit a partial function $f$ that matches this upper bound, $\text{fbs}(f) =
\Omega(\sqrt{n \cdot \text{bs}(f)})$.