Chicago Journal of Theoretical Computer Science

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


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:
  1. 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).$
  2. 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 super-quadratic separation between the block sensitivity and the sensitivity.

  3. 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 two-sided 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).
  4. We show that the (non-negative 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.

Submitted March 7, 2014, revised March 24, 2016, and in final form July 15, 2016, published July 20, 2016.

DOI: 10.4086/cjtcs.2016.008

[] Volume 2016, Article 7 [] Article 9
[back] Volume 2016 [back] Published articles
[CJCTS home]