Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-051 | 21st July 2019 10:38

Coin Flipping in Dynamic Programming Is Almost Useless

RSS-Feed




Revision #1
Authors: Stasys Jukna
Accepted on: 21st July 2019 10:38
Downloads: 36
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR18-051 | 15th March 2018 23:25

Derandomizing Dynamic Programming and Beyond





TR18-051
Authors: Stasys Jukna
Publication: 15th March 2018 23:26
Downloads: 494
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint