Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FRACTIONAL BLOCK SENSITIVITY:
Reports tagged with fractional block sensitivity:
TR17-123 | 2nd August 2017
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Quadratically Tight Relations for Randomized Query Complexity

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>


TR17-150 | 26th September 2017
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs

All Classical Adversary Methods are Equivalent for Total Functions

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint