Randomized and deterministic query complexity of symmetric functions

Question

The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query complexity? Do we have $R_{1/4}(f) = \Omega(n)$?

I know it's true for some well-known functions (like the OR function), and that it doesn't hold in the quantum setting (for instance, $Q(OR) = \Theta(\sqrt{n})$ by Grover's algorithm). In fact, $D(f) = O(Q(f)^2)$ so we have at least $R_{1/4}(f) = \Omega(\sqrt{n})$.

Answer 1

Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf

The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. However, $D(f) \geq s(f)$ and $R_{1/4}(f) \geq \frac{s(f)}{3}$...

There are other interesting results concerning symmetric functions in this survey (see Section 6.1).