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.
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ 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 $\endgroup$– mathworker21Oct 16, 2021 at 9:53
-
$\begingroup$ @mathworker21 You are right. We can assume that at most one variable is true. $\endgroup$– domotorpOct 16, 2021 at 16:16
-
$\begingroup$ @domotorp Thanks. Yes, I should have said "at most one" instead (otherwise, just always outputting 'true' satisfies the family I gave). $\endgroup$– mathworker21Oct 16, 2021 at 20:46
-
1$\begingroup$ 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. $\endgroup$– user2316602Oct 17, 2021 at 10:13
-
1$\begingroup$ ... which is why I would prefer to cite instead of writing it up. $\endgroup$– user2316602Oct 17, 2021 at 10:14
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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