Published by the Department of Computer Science, The University of Chicago.

Abstract

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.

• The article: PDF (230 KB)
• Source material: ZIP (81KB)
• BibTeX entry for this article (262 bytes)

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

© Rahgav Kulkarni and Avishai Tal
Licensed under a Creative Commons Attribution License

Volume 2016, Article 7

Article 9

Volume 2016

Published articles