ECCC-Report TR13-168https://eccc.weizmann.ac.il/report/2013/168Comments and Revisions published for TR13-168en-usTue, 03 Dec 2013 08:59:21 +0200
Comment 1
| On Fractional Block Sensitivity |
Raghav Kulkarni,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/168#comment1In 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.Tue, 03 Dec 2013 08:59:21 +0200https://eccc.weizmann.ac.il/report/2013/168#comment1
Revision 1
| On Fractional Block Sensitivity |
Raghav Kulkarni,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/168#revision1In 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.Sat, 30 Nov 2013 04:34:13 +0200https://eccc.weizmann.ac.il/report/2013/168#revision1
Paper TR13-168
| On Fractional Block Sensitivity |
Raghav Kulkarni,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/168In 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.Fri, 29 Nov 2013 21:13:14 +0200https://eccc.weizmann.ac.il/report/2013/168