16

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 ?

Piotr
  • 971
  • 7
  • 15

1 Answers1

7

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

arnab
  • 7,000
  • 1
  • 38
  • 55
  • Thanks, Arnab! Is there a reference for this or similar arguments ? – Piotr Aug 25 '10 at 23:22
  • 4
    I finally found the paper where I'd seen this argument! It's "Weak derandomization of weak algorithms" (http://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. – arnab Aug 26 '10 at 03:25