Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-051 | 15th March 2018 23:25

Derandomizing Dynamic Programming and Beyond

RSS-Feed




TR18-051
Authors: Stasys Jukna
Publication: 15th March 2018 23:26
Downloads: 319
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