In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and Gilmer, Saks, and Srinivasan (CCC, 2013) 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 (CCC, 2003). In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity $s(f)$ and approximate degree $\widetilde \deg(f)$. As a consequence we obtain the following results:
(1) We show that $\widetilde \deg(f) = \Omega(\sqrt{RC(f)}),$ solving an open question posed by Aaronson. This also implies
that $\tilde \deg(f) = \Omega(QC(f)),$ where $QC(f)$ is the quantum certificate complexity of $f$.
As both $\tilde \deg(f)$ and $\QC(f)$ serve as lower bounds for the bounded error quantum query complexity, this
shows that $\tilde \deg(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 $\tilde \deg(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, Yao, and Zhang 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 better than 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$. This improves the previous best relation between these two complexity measures given by Midrijanis of $R_2(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 \emph{bounded error quantum query complexity} of
$f$ can not 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 second author's name was accidentally missing from the previous version. This is corrected in this version.
Abstract is cleaned up.
In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and
Gilmer, Saks, and Srinivasan (CCC, 2013) 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 (CCC, 2003). In this paper, we relate the fractional block sensitivity to other complexity measures
such as sensitivity $s(f)$ and approximate degree $\tilde \deg(f)$. As a consequence we obtain the following results:
(1) We show that $\tilde \deg(f) = \Omega(\sqrt{RC(f)}),$ solving an open question posed by Aaronson. This also implies
that $\tilde \deg(f) = \Omega(QC(f)),$ where $QC(f)$ is the quantum certificate complexity of $f$.
As both $\tilde \deg(f)$ and $\QC(f)$ serve as lower bounds for the bounded error quantum query complexity, this
shows that $\tilde \deg(f)$ is always a tighter lower bound compared to $\QC(f).$
\item
\begin{enumerate}
\item
We show that every transitive function on $n$ variables must have $\RC(f) = \Omega(n^{1/2})$, $\QC(f) = \Omega(n^{1/4})$
and $\tilde \deg(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, Yao, and Zhao and Sun.
\item
We show that Chakraborty's example of a transitive function with $\s(f) = O(n^{1/3})$ is optimal unless
there is better than quadratic separation between the block sensitivity and the sensitivity.
\end{enumerate}
\item
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 \emph{two-sided bounded error randomized decision
tree complexity} of $f$. This improves the previous best relation between these two complexity measures given by
Midrijanis of $R_2(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 \emph{bounded error quantum query complexity} of
$f$ can not 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.
In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal (ITCS, 2013) and Gilmer, Saks, and Srinivasan (CCC, 2013) 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 (CCC, 2003). In this paper, we relate the fractional block sensitivity to other complexity measures
such as sensitivity $s(f)$ and approximate degree $\tilde \deg(f)$. As a consequence we obtain the following results:
(1) We show that $\widetilde \deg(f) = \Omega(\sqrt{RC(f)}),$ solving an open question posed by Aaronson. This also implies
that $\widetilde \deg(f) = \Omega(QC(f)),$ where $QC(f)$ is the quantum certificate complexity of $f$.
As both $\widetilde \deg(f)$ and $\QC(f)$ serve as lower bounds for the bounded error quantum query complexity, this
shows that $\tilde \deg(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 $\tilde \deg(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, Yao, and Zhang 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 better than quadratic separation between the block sensitivity and the sensitivity.
(3) Using fractional block sensitivity, we show that the \emph{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$. This improves the previous best relation between these two complexity measures given by
Midrijanis of $R_2(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$ can not 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.
