文章基本信息

标题：On Fractional Block Sensitivity
本地全文：下载
作者：Raghav Kulkarni ; Avishay Tal
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-16
DOI：10.4086/cjtcs.2016.008
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal and Gilmer, Saks, and Srinivasan 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. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity $s(f)$ and approximate degree $adeg(f)$. As a consequence we obtain the following results: 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).$ 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.
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). 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
关键词：decision tree complexity; fractional block sensitivity; sensitivity; approximate;degree