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

<p>*: 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...</p>

CC BY-SA 2.5
2010-08-25T23:22:30.803Z
Thanks, Arnab! Is there a reference for this or similar arguments ?
Piotr
CC BY-SA 2.5
2010-08-26T03:25:28.920Z
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
CC BY-SA 2.5
2010-08-25T10:24:34.080Z
2010-08-25T19:49:40.320Z
2010-08-25T19:49:40.320Z
arnab
<p><em>Adleman, FOCS'78</em> 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  ?</p>

<derandomization>
More efficient non-uniform derandomization ?
Piotr
# More efficient non-uniform derandomization ?

(Asked by: username_0 on 2010-08-25)

*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 ?

**Tags:** derandomization

---

## 1 answers

### Answer by username_1 on 2010-08-25. Score: 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...

> **Comments:**
> **username_0**: Thanks, Arnab! Is there a reference for this or similar arguments ?  
> **username_1**: 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.  

---

