Volume 2016
Article 8
Published by the Department of Computer Science, The University of Chicago.
On Fractional Block Sensitivity
Raghav Kulkarni
Centre for Quantum Technologies,
National University of Singapore,
Singapore;
kulraghav AT gmail DOT com
Avishay Tal
School of Mathematics,
Institute for Advanced Study, Princeton, NJ, USA;
avishay DOT tal AT gmail DOT com
July 20, 2016
Abstract
In this paper we study the fractional block sensitivity
of Boolean functions.
Recently, Tal and Gilmer, Saks, and Srinivasan independently
introduced this complexity measure, denoted by fbs(f), and showed that it
is equal (up to a constant factor) to the
randomized certificate complexity,
denoted by RC(f), which was introduced by Aaronson.
In this paper, we relate the fractional block sensitivity to other complexity
measures such as sensitivity $s(f)$ and approximate degree
$adeg(f)$. As a
consequence we obtain the following results:
 We show that $adeg(f) = \Omega(\sqrt{RC(f)}),$
solving an open question posed by Aaronson. This also implies that
$adeg(f) = \Omega(QC(f)),$ where $QC(f)$ is the quantum certificate complexity of $f.$
As both $adeg(f)$ and $QC(f)$ serve as lower bounds for the
bounded error quantum query complexity, this shows that $adeg(f)$ is always
a tighter lower bound compared to $QC(f).$

a. We show that every transitive function on $n$ variables must have $RC(f) = \Omega(n^{1/2})$, $QC(f) = \Omega(n^{1/4})$ and $adeg(f) = \Omega(n^{1/4})$, and note
that all these bounds are tight. This is a strengthening of the previous lower bounds given by Sun et al., and Sun.
b. We show that Chakraborty's example of a transitive function with $s(f) = O(n^{1/3})$ is optimal unless there is a superquadratic separation between the block sensitivity and the sensitivity.

Using fractional block sensitivity, we show that the
zero error randomized decision tree complexity, $R_0(f)$, is upper bounded by $O(R_2(f)^2 \cdot \log R_2(f))$ where $R_2(f)$ is the
twosided bounded error randomized decision tree complexity of $f$.
The previous best relation between these two complexity measures was cubic,
although Midrijanis showed $R_0(f) = O(R_2(f)^2 \cdot \log n)$
(where $n$ is the number of variables).

We show that the (nonnegative weight) adversary methods to lower bound the
bounded error quantum query complexity of $f$ cannot give better
bounds than $\sqrt{RC^0(f) RC^1(f)}.$
This refines the earlier bound of $\sqrt{c^0(f) c^1(f)}$ by Spalek and Szegedy
and strengthens the so called certificate complexity barrier
to its randomized analogue.
 The article: PDF (230 KB)
 Source material: ZIP (81KB)
 BibTeX entry for this
article (262 bytes)
Submitted March 7, 2014, revised March 24, 2016, and in final form July 15, 2016, published July 20, 2016.
Volume 2016, Article 7
Article 9
Volume 2016
Published articles