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 deg(f). As a consequence we obtain the following results:

(1) We show that deg(f)=(RC(f)) solving an open question posed by Aaronson. This also impliesthat deg(f)=(QC(f)) where QC(f) is the quantum certificate complexity of f.As both deg(f) and \QC(f) serve as lower bounds for the bounded error quantum query complexity, thisshows that 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)=(n12) , \QC(f)=(n14) and deg(f)=(n14) , and note that all these bounds are tight. This is a strengthening of theprevious 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(n13) is optimal unlessthere 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, R0(f), isupper bounded by O(R2(f)2logR2(f)) where R2(f) is the two-sided bounded error randomized decisiontree complexity of f. This improves the previous best relation between these two complexity measures given by Midrijanis of R2(f)=O(R2(f)2logn) (where n is the number of variables.

(4) We show that the (non-negative weight) adversary methods tolower bound the \emph{bounded error quantum query complexity} off can not give better bounds than \RC0(f)\RC1(f) This refines the earlier bound of \c0(f)\c1(f) bySpalek and Szegedy and strengthens the so calledcertificate complexity barrier to its randomized analogue