We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description
complexity as gates. In particular, such circuits can use allarithmetic operations +,-,x,/, optimization operations min and max, conditional branching (if-then-else), and many
more. We show that probabilistic circuits using any of theseoperations as gates can be simulated by deterministic circuits with only about a quadratical blowup in size. A not much larger blow up in circuit size is also shown when derandomizing approximating circuits. The algorithmic consequence, motivating the title, is that randomness cannot substantially speed up dynamic programming algorithms.

Correction: as one of the referees observed, upper bounds on the number of zero-patterns of polynomial are not enough for our purposes. Knowing only p=0 or p!=0 in Lemma 5.4 is not enough to decide which of p=0, p<0 and p>0 do really happened. And, in fact, there can be exponentially more sign patterns than ero patterns, in general. So, we now use the bounds of sign-patterns instead. [The direct derandomiation of arithmetic circuits Sect. 10 is not affected; the proof now appeared in Amer. Math. Monthly, 126:4 (2019) 364-366.] New results: (1) derandomization of approximating circuits (Sect. 5), and (2) removal of the "constant-freenes" condition of circuits in the case of one-sided error (Appendix D). The presentation is made more structured, the need of Haussler's theorem is eliminated (we now directly combine Warren's upper bound on sign-patterns with the original theorem by Vapnik and Chervonenkis of 1971), measurability issues are now shortly discussed (Appendix B). Since, as we now show, even approximating circuits allow derandomization, the title is also changed.

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. In arithmetic circuits, randomization cannot spare even one single gate.