<p>After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I may cite for this fact, I am still interested.</p>
<p>[1] <a href="https://people.cs.rutgers.edu/%7Esa1497/courses/cs514-s20/lec3.pdf" rel="nofollow noreferrer">https://people.cs.rutgers.edu/~sa1497/courses/cs514-s20/lec3.pdf</a></p>

CC BY-SA 4.0
2021-10-23T12:01:46.103Z
2021-10-23T12:01:46.103Z
user2316602
<p>Let us have booleans <span class="math-container">$x_1, \cdots, x_n$</span>. Any algorithm that determines <span class="math-container">$\bigvee_1^n x_i$</span> with probability at least <span class="math-container">$2/3$</span> requires <span class="math-container">$\Omega(n)$</span> time. It is not too difficult to prove this, but the proof would certainly be more than a few lines. I have seen a paper that proves this, but cannot find it. Does anyone know of such a paper? I need this in my paper (I am doing a reduction from this problem) and would prefer not to repeat the argument if someone has written it up in detail already. Any result which would imply this in a few lines would be useful, too.</p>

CC BY-SA 4.0
2021-10-16T09:53:49.337Z
what if some $x_j$ is true and all the others are false? doesn't that show an $\Omega(n)$ lower bound? i could be wrong
mathworker21
CC BY-SA 4.0
2021-10-16T16:16:58.993Z
@mathworker21 You are right. We can assume that at most one variable is true.
domotorp
CC BY-SA 4.0
2021-10-16T20:46:44.600Z
@domotorp Thanks. Yes, I should have said "at most one" instead (otherwise, just always outputting 'true' satisfies the family I gave).
mathworker21
CC BY-SA 4.0
2021-10-17T10:13:59.070Z
That is not a formal proof. While what you are suggesting works directly for deterministic algorithms, the lower bound for randomized algorithms is slightly more technical.
user2316602
CC BY-SA 4.0
2021-10-17T10:14:26.147Z
... which is why I would prefer to cite instead of writing it up.
user2316602
CC BY-SA 4.0
2021-10-23T22:23:59.173Z
Can't you obtain this from the $\Theta(n)$ (randomized) communication complexity of Set Disjointness (for which a citation is easy to find)?
Clement C.
<reference-request><time-complexity><lower-bounds><sample-complexity>
Lower bound for the OR problem
user2316602
# Lower bound for the OR problem

(Asked by: username_0 on 2021-10-16)

Let us have booleans $x\_1, \cdots, x\_n$. Any algorithm that determines $\bigvee\_1^n x\_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof would certainly be more than a few lines. I have seen a paper that proves this, but cannot find it. Does anyone know of such a paper? I need this in my paper (I am doing a reduction from this problem) and would prefer not to repeat the argument if someone has written it up in detail already. Any result which would imply this in a few lines would be useful, too.

**Tags:** reference-request, time-complexity, lower-bounds, sample-complexity

> **Comments:**
> **username_1**: what if some $x_j$ is true and all the others are false? doesn't that show an $\Omega(n)$ lower bound? i could be wrong  
> **username_2**: @username_1 You are right. We can assume that at most one variable is true.  
> **username_1**: @username_2 Thanks. Yes, I should have said "at most one" instead (otherwise, just always outputting 'true' satisfies the family I gave).  
> **username_0**: That is not a formal proof. While what you are suggesting works directly for deterministic algorithms, the lower bound for randomized algorithms is slightly more technical.  
> **username_0**: ... which is why I would prefer to cite instead of writing it up.  
> **username_3**: Can't you obtain this from the $\Theta(n)$ (randomized) communication complexity of Set Disjointness (for which a citation is easy to find)?  

---

## 1 answers

### Answer by username_0 on 2021-10-23. Score: 2 | Accepted answer

After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I may cite for this fact, I am still interested.

[1] [https://people.cs.rutgers.edu/~sa1497/courses/cs514-s20/lec3.pdf](https://people.cs.rutgers.edu/%7Esa1497/courses/cs514-s20/lec3.pdf)


---

