<p>Ok, I found the answer in this survey: <a href="http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf" rel="nofollow">http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf</a></p>

<p>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}$...</p>

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

CC BY-SA 3.0
2016-05-09T16:13:28.970Z
2016-05-09T16:13:28.970Z
permanganate
<p>The deterministic query complexity $D(f)$ of a <strong>symmetric</strong> 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)$?</p>

<p>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). <a href="http://portal.acm.org/citation.cfm?id=502097" rel="nofollow">In fact</a>, $D(f) = O(Q(f)^2)$ so we have at least $R_{1/4}(f) = \Omega(\sqrt{n})$.</p>

<randomized-algorithms><query-complexity><decision-trees>
Randomized and deterministic query complexity of symmetric functions
permanganate
# Randomized and deterministic query complexity of symmetric functions

(Asked by: username_0 on 2016-05-09)

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](http://portal.acm.org/citation.cfm?id=502097), $D(f) = O(Q(f)^2)$ so we have at least $R\_{1/4}(f) = \Omega(\sqrt{n})$.

**Tags:** randomized-algorithms, query-complexity, decision-trees

---

## 1 answers

### Answer by username_0 on 2016-05-09. Score: 1 | Accepted answer

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).


---

