{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:37:08Z","timestamp":1787341028094,"version":"build-2736575974"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218547"],"award-info":[{"award-number":["1218547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1452302"],"award-info":[{"award-number":["1452302"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1705028"],"award-info":[{"award-number":["1705028"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (nonuniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with similar run-time to the original randomized algorithms. The amplification technique applies when there is a quick, probabilistic test of the randomness. In this case, we show how to efficiently find one randomness string for the algorithm that works with very high probability and apply the algorithm only on that randomness (in contrast, standard approaches suggest a number of possible randomness strings and run the algorithm on all of them). The search of good randomness turns out to be a natural stochastic multiarmed bandit problem, which we define (``the biased coin problem'') and analyze. The derandomization technique applies when there is a verifier that can test the randomness of the algorithm while only inspecting a sublinear size sketch of the input (the sketch may be hard to compute; the verifier may be inefficient and is allowed to reject a small portion of the good randomness strings). In this case, we show how to apply Adleman's derandomization (from the proof of $BPP\\subseteq P\/poly$) more efficiently. We demonstrate the techniques by showing applications for dense max-cut, approximate clique, free games, and going from list decoding to unique decoding for Reed--Muller codes.<\/jats:p>","DOI":"10.1137\/17m1110596","type":"journal-article","created":{"date-parts":[[2020,10,8]],"date-time":"2020-10-08T14:07:46Z","timestamp":1602166066000},"page":"959-998","source":"Crossref","is-referenced-by-count":2,"title":["Amplification and Derandomization without Slowdown"],"prefix":"10.1137","volume":"49","author":[{"given":"Ofer","family":"Grossman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Moshkovitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,10,8]]},"reference":[{"key":"atypb1","first-page":"44","author":"Aaronson S.","year":"2014","journal-title":"Washington, DC"},{"key":"atypb2","first-page":"75","author":"Adleman L.","year":"1978","journal-title":"Washington, DC"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850097"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00008-4"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040109"},{"key":"atypb8","first-page":"284","author":"Arora S.","year":"1995","journal-title":"New York"},{"key":"atypb9","first-page":"512","author":"Barak B.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb10","first-page":"409","author":"Baran I.","year":"2005","journal-title":"Heidelberg"},{"key":"atypb11","first-page":"40","author":"Braverman M.","year":"2010","journal-title":"Washington, DC"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/110846373"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000200"},{"key":"atypb15","first-page":"255","author":"Even-Dar E.","year":"2002","journal-title":"Heidelberg"},{"key":"atypb16","unstructured":"U. Feige,\n                      Error Reduction by Parallel Repetition-The State of the Art\n                      , Technical report, Weizmann Science Press, Jerusalem, Israel, 1995."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.006"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000049"},{"key":"atypb19","unstructured":"J. Fox, L. M. Lov\u00e1sz, and Y. Zhao,\n                      A Fast New Algorithm for Weak Graph Regularity\n                      , preprint,https:\/\/arxiv.org\/abs\/1801.05037, 2018."},{"key":"atypb20","first-page":"12","author":"Frieze A.","year":"1996","journal-title":"Washington, DC"},{"key":"atypb21","unstructured":"E. Gat and S. Goldwasser,\n                      Probabilistic search algorithms with unique answers and their cryptographic applications\n                      , in Electronic Colloquium on Computational Complexity (ECCC), Weizmann Institute of Science, Jerusalem, Israel, 2011, TR11-136."},{"key":"atypb22","unstructured":"O. Goldreich,\n                      A Sample of Samplers-A Computational Perspective on Sampling (Survey)\n                      , Technical report, ECCC Report TR97-020, Weizmann Institute of Science, Jerusalem, Israel, 1997."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"atypb26","first-page":"111","author":"Impagliazzo R.","year":"2012","journal-title":"Washington, DC"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0036-8"},{"key":"atypb28","first-page":"220","author":"Impagliazzo R.","year":"1997","journal-title":"New York"},{"key":"atypb29","first-page":"248","author":"Impagliazzo R.","year":"1989","journal-title":"Washington, DC"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996762"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196134"},{"key":"atypb33","first-page":"767","author":"Khot S.","year":"2002","journal-title":"New York"},{"key":"atypb34","first-page":"162","author":"Luby M.","year":"1988","journal-title":"Washington, DC"},{"key":"atypb35","first-page":"623","volume":"5","author":"Mannor S.","year":"2004","journal-title":"J. Mach. Learn. Res."},{"key":"atypb36","unstructured":"P. Manurangsi and D. Moshkovitz,\n                      Approximating dense max 2-CSPs\n                      , in APPROX-RANDOM 2015, Princeton, NJ, 2015."},{"key":"atypb37","unstructured":"C. Mathieu and W. Schudy,\n                      Yet another algorithm for dense max cut: Go greedy\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, CA, 2008, pp. 176-182."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/100811623"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505243"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0006-4"},{"key":"atypb42","first-page":"110","volume":"2","author":"Subbotovskaya B. A.","year":"1961","journal-title":"Sov. Math. Dokl."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"atypb45","first-page":"399","author":"Szemer\u00e9di E.","year":"1978","journal-title":"France"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0273-5"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0243-3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1110596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:01:50Z","timestamp":1787338910000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1110596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/17M1110596"],"URL":"https:\/\/doi.org\/10.1137\/17m1110596","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}