Adleman, FOCS'78 showed that any randomized circuit for inputs of length $n$ can be non-uniformly derandomized. However, the construction effectively duplicates the original circuit $O(n)$ times, so the derandomized circuit is larger than the original one by a factor of $O(n)$. Is there any more efficient construction out there that multiplies the circuit size by a smaller factor ?


1 Answer 1


I don't think something much better is known. Because for example, if it were possible to derandomize circuits with only a sublinear blowup, then I think it would also be possible to non-trivially (but non-uniformly*) derandomize communication protocols. And I don't believe the latter is known. Adleman's proof gives a linear blowup as you say, so that the derandomization of communication protocols is trivial because it would give a linear blowup in the communication complexity.

*: By "non-uniform" in the context of communication protocols, I mean the algorithm for the two parties to compute the next bit to send to the other is not explicit. I recall reading a discussion about this in some paper, but I can't seem to find a reference now...

  • $\begingroup$ Thanks, Arnab! Is there a reference for this or similar arguments ? $\endgroup$
    – Piotr
    Aug 25, 2010 at 23:22
  • 4
    $\begingroup$ I finally found the paper where I'd seen this argument! It's "Weak derandomization of weak algorithms" (cs.haifa.ac.il/~ronen/online_papers/PID888174.pdf) by Ronen Shaltiel. The paper talks about uniform derandomization. But some of the discussion is quite relevant. See Footnote 3 on page 2. $\endgroup$
    – arnab
    Aug 26, 2010 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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