Coin Flipping in Dynamic Programming Is Almost Useless

2020/06/01 by Stasys Jukna
Computer Science · Mathematics · #Algorithm #Arithmetic #Bounded function #Coin flipping #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computer science #Dynamic programming #Electronic circuit #Machine Learning and Algorithms #Mathematics #Probabilistic logic #Randomness #Theoretical computer science #Theory of computation #cs.CC

paper · pdf · doi:10.1145/3397476

published in ACM Transactions on Computation Theory 12(3), 1-26 (Association for Computing Machinery) · 25 pages, 1 table

openalex publication_date 2020/06/01 · arxiv created 2020/12/23 · arxiv updated 2020/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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 all arithmetic operations (+, −, ×, ÷), optimization operations (min and max), conditional branching (if-then-else), and many more. We show that probabilistic circuits using any of these operations as gates can be simulated by deterministic circuits with only about a quadratical blowup in size. A slightly larger blowup 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.

Citations

• Probabilistic algorithms for sparse polynomials
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Relative to a Random OracleA, \bf P^A ≠ \bf NP^A ≠ co-\bf NP^A with Probability 1
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities