All reports by Author Jevgenijs Vihrovs:

__
TR17-150
| 26th September 2017
__

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs#### All Classical Adversary Methods are Equivalent for Total Functions

Revisions: 2

__
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

__
TR14-077
| 2nd June 2014
__

Andris Ambainis, Jevgenijs Vihrovs#### Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma

Revisions: 2

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs

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

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

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

Andris Ambainis, Jevgenijs Vihrovs

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>