Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR17-150 | 12th November 2018 15:49

All Classical Adversary Methods are Equivalent for Total Functions

RSS-Feed




Revision #2
Authors: Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs, Aleksejs Zajakins
Accepted on: 12th November 2018 15:49
Downloads: 8
Keywords: 


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. For partial functions, we show unbounded separations between $\text{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 \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)})$.


Revision #1 to TR17-150 | 12th November 2018 15:47

All Classical Adversary Methods are Equivalent for Total Functions





Revision #1
Authors: Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs
Accepted on: 12th November 2018 15:47
Downloads: 11
Keywords: 


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)})$.



Changes to previous version:

Now includes a proof of separation between CRA and CRA1. Also added a simplified proof of Theorem 15.


Paper:

TR17-150 | 26th September 2017 16:02

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. For partial functions, we show unbounded separations between $\text{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 \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)})$.



ISSN 1433-8092 | Imprint