6
$\begingroup$

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.

$\endgroup$
7
  • 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$ Oct 16 '21 at 9:53
  • $\begingroup$ @mathworker21 You are right. We can assume that at most one variable is true. $\endgroup$
    – domotorp
    Oct 16 '21 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$ Oct 16 '21 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$ Oct 17 '21 at 10:13
  • 1
    $\begingroup$ ... which is why I would prefer to cite instead of writing it up. $\endgroup$ Oct 17 '21 at 10:14
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.