Zobrazeno 1 - 1
of 1
pro vyhledávání: '"Zajakins, Aleksejs"'
Autor:
Ambainis, Andris, Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs, Zajakins, Aleksejs
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 an
Externí odkaz:
http://arxiv.org/abs/1709.08985
