Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-168 | 30th November 2013 04:34

On Fractional Block Sensitivity

RSS-Feed




Revision #1
Authors: Raghav Kulkarni, Avishay Tal
Accepted on: 30th November 2013 04:34
Downloads: 3398
Keywords: 


Abstract:

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.



Changes to previous version:

The second author's name was accidentally missing from the previous version. This is corrected in this version.
Abstract is cleaned up.


Paper:

TR13-168 | 29th November 2013 18:00

On Fractional Block Sensitivity


Abstract:

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.


Comment(s):

Comment #1 to TR13-168 | 3rd December 2013 08:59

On Fractional Block Sensitivity





Comment #1
Authors: Raghav Kulkarni, Avishay Tal
Accepted on: 3rd December 2013 08:59
Downloads: 1748
Keywords: 


Abstract:

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.




ISSN 1433-8092 | Imprint