ECCC-Report TR17-150https://eccc.weizmann.ac.il/report/2017/150Comments and Revisions published for TR17-150en-usMon, 12 Nov 2018 15:49:30 +0200
Revision 2
| All Classical Adversary Methods are Equivalent for Total Functions |
Andris Ambainis,
Martins Kokainis,
Krisjanis Prusis,
Jevgenijs Vihrovs,
Aleksejs Zajakins
https://eccc.weizmann.ac.il/report/2017/150#revision2We 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)})$.Mon, 12 Nov 2018 15:49:30 +0200https://eccc.weizmann.ac.il/report/2017/150#revision2
Revision 1
| All Classical Adversary Methods are Equivalent for Total Functions |
Andris Ambainis,
Martins Kokainis,
Krisjanis Prusis,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2017/150#revision1We 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)})$.Mon, 12 Nov 2018 15:47:11 +0200https://eccc.weizmann.ac.il/report/2017/150#revision1
Paper TR17-150
| All Classical Adversary Methods are Equivalent for Total Functions |
Andris Ambainis,
Martins Kokainis,
Krisjanis Prusis,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2017/150We 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)})$.Sun, 08 Oct 2017 08:06:26 +0300https://eccc.weizmann.ac.il/report/2017/150