Given $\sqrt{n}$ numbers of $n$ bits each. I need to find its OR and store it at another number RESULT of $n$ bits. Trivially it can be done in $\mathcal{O}(n \sqrt{n})$ time, or $\mathcal{O}(n \sqrt{n} \,/ \log n)$ considering RAM model with word size $\log n$.

I am interested in some deterministic or randomized solution that takes $\mathcal{O}(n \text{ polyLog } n)$ time expected or exact to solve the problem. I need an exact solution but expected time will work.

  • 5
    $\begingroup$ What makes you think it is possible to achieve what you want? It will take $\Omega(n \sqrt{n})$ time (or $\Omega(n \sqrt{n}/\lg n)$ time) just to read all of the bits, and it seems obvious that there are problem instances where you need to read all of the bits. For instance, consider a problem instance where all of the numbers are zero, or where all the numbers are zero except one has a single bit set. P.S. When you say "expected time", are you also averaging over all possible inputs? $\endgroup$ – D.W. Jun 30 '14 at 22:00
  • $\begingroup$ That is true. I am not averaging overall inputs. That is why I am asking for randomized solution rather than deterministic. I don't understand how this lower bound works in randomized setting. Can you please elaborate why your argument also works in the randomized setting. Thnx. $\endgroup$ – sbzk Jul 1 '14 at 9:19
  • 3
    $\begingroup$ @sbzk, I think Yao's lemma works here: Consider the set of instances with just one bit set to $1$, and suppose your input is uniformly drawn from these instances. The average performance of the best deterministic algorithm on this distribution bounds the performance of the best randomized algorithm on its worst-case instance from this input set. I think you could formally show that every deterministic algorithm needs to read $\Omega($all$)$ the bits on average. $\endgroup$ – usul Jul 1 '14 at 14:05

Your Answer

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

Browse other questions tagged or ask your own question.