Revision #1 Authors: Raghav Kulkarni, Avishay Tal

Accepted on: 30th November 2013 04:34

Downloads: 3374

Keywords:

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.

TR13-168 Authors: Raghav Kulkarni, Avishay Tal

Publication: 29th November 2013 21:13

Downloads: 2686

Keywords:

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 #1 Authors: Raghav Kulkarni, Avishay Tal

Accepted on: 3rd December 2013 08:59

Downloads: 1722

Keywords:

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.