16
$\begingroup$

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 ?

$\endgroup$
7
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Thanks, Arnab! Is there a reference for this or similar arguments ? $\endgroup$ – Piotr Aug 25 '10 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 '10 at 3:25

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.