{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:23Z","timestamp":1750220783014,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["JU3105\/1-2"],"award-info":[{"award-number":["JU3105\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>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 (+, \u2212, \u00d7, \u00f7), 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.<\/jats:p>","DOI":"10.1145\/3397476","type":"journal-article","created":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T10:13:38Z","timestamp":1591006418000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Coin Flipping in Dynamic Programming Is Almost Useless"],"prefix":"10.1145","volume":"12","author":[{"given":"Stasys","family":"Jukna","sequence":"first","affiliation":[{"name":"Vilnius University, Akademijos, Vilnius, Lithuania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.37"},{"volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC). 471--474","author":"Ajtai M.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00143892"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007447530834"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1016"},{"volume-title":"Proceedings of the 27th Annual ACM Symposium. on Theory of Computing (STOC). 335--342","author":"Cucker F.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.  D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"volume-title":"Lecture Notes in Mathematics","author":"Dudley R. M.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993408"},{"key":"e_1_2_1_13_1","volume-title":"Studies in Complexity and Cryptography. Lecture Notes in Computer Science","volume":"6650","author":"Goldreich O.","year":"2011"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050002"},{"volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC). 76--85","author":"Grigoriev D.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270387"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing (STOC). 220--229","author":"Impagliazzo R.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3838"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/320941.320945"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90079-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1964-0161339-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.  M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_24_1","unstructured":"H. Morizumi. 2012. Limiting Negations in Probabilistic Circuits. New Trends in Algorithms and Theory of Computation Departmental Bulletin Paper 1799 pages 81--83. Kyoto University Research Information Repository.  H. Morizumi. 2012. Limiting Negations in Probabilistic Circuits. New Trends in Algorithms and Theory of Computation Departmental Bulletin Paper 1799 pages 81--83. Kyoto University Research Information Repository."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press.  R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"D. Pollard. 1984. Convergence of Stochastic Processes. Springer-Verlag.  D. Pollard. 1984. Convergence of Stochastic Processes. Springer-Verlag.","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204724"},{"key":"e_1_2_1_28_1","first-page":"49","article-title":"Progress on polynomial identity testing","volume":"99","author":"Saxena N.","year":"2009","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969640"},{"key":"e_1_2_1_31_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka A.","year":"2010","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90210-5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"A. Tarski. 1951. A Decision Method for Elementary Algebra and Geometry (2nd ed.). University of California Press Berkeley and Los Angeles Calif.  A. Tarski. 1951. A Decision Method for Elementary Algebra and Geometry (2nd ed.). University of California Press Berkeley and Los Angeles Calif.","DOI":"10.1525\/9780520348097"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"},{"volume-title":"Lecture Notes in Computer Science","author":"Zippel R.","key":"e_1_2_1_36_1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397476","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397476","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:33Z","timestamp":1750200093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3397476"],"URL":"https:\/\/doi.org\/10.1145\/3397476","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}