{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:19Z","timestamp":1787337559549,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>We derive a stronger consequence of $\\mathsf{EXP}$ (deterministic exponential time) having polynomial-size circuits than was known previously, namely that for each language $L \\in \\mathsf{P}$ (polynomial time), and for each efficiently decidable error-correcting code E having nontrivial relative distance, there is a simulation of L in Merlin-Arthur polylogarithmic time that fools all deterministic polynomial-time adversaries for inputs that are codewords of E. Using the connection between circuit lower bounds and derandomization, we obtain uniform assumptions for derandomizing $\\mathsf{BPP}$ (probabilistic polynomial time). Our results strengthen the space-randomness tradeoffs of Sipser [J. Comput. System Sci., 36 (1988), pp. 379--383], Nisan and Wigderson [J. Comput. System Sci.}, 49 (1994), pp. 149--167], and Lu [Comput. Complexity, 10 (2001), pp. 247--259].<\/jats:p>\n                  <jats:p>We also consider a more quantitative notion of simulation, where the measure of success of the simulation is the fraction of inputs of a given length on which the simulation works. Among other results, we show that if there is no polynomial-time bound t such that $\\mathsf{P}$ can be simulated well by Merlin-Arthur machines operating in time t, then for any $\\epsilon &gt; 0$ there is a simulation of $\\mathsf{BPP}$ in $\\mathsf{P}$ that works for all but $2^{n^{\\epsilon}}$ inputs of length n. This is a uniform strengthening of a recent result of Goldreich and Wigderson [ Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, 2002, pp. 209--223].<\/jats:p>\n                  <jats:p>\n                    Finally, we give an unconditional simulation of multitape Turing machines operating in probabilistic time t by Turing machines operating in deterministic time o(2\n                    <jats:sup>t<\/jats:sup>\n                    ). We show similar results for randomized $\\mathsf{NC}^{1}$ circuits.\n                  <\/jats:p>\n                  <jats:p>Our proofs are based on a combination of techniques in the theory of derandomization with results on holographic proofs.<\/jats:p>","DOI":"10.1137\/s0097539703438629","type":"journal-article","created":{"date-parts":[[2005,10,5]],"date-time":"2005-10-05T21:00:22Z","timestamp":1128546022000},"page":"59-90","source":"Crossref","is-referenced-by-count":13,"title":["Holographic Proofs and Derandomization"],"prefix":"10.1137","volume":"35","author":[{"given":"Dieter","family":"van Melkebeek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Eric Allender, Vivek Gore, On strong separations from AC0 (extended abstract), Lecture Notes in Comput. Sci., Vol. 529, Springer, Berlin, 1991, 1\u2013151136065","DOI":"10.1007\/3-540-54458-5_44"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"R3","unstructured":"M. Agrawal, N. Kayal, and N. Saxena,\n                      PRIMES is in P\n                      , Technical report, Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, India, 2002."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-75357-2"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy,\n                      Checking computations in polylogarithmic time\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, 1991, ACM, New York, pp. 21\u201332.","DOI":"10.1145\/103418.103428"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Z. Bar\u2010Yossef, O. Goldreich, and A. Wigderson,\n                      Deterministic amplification of space\u2010bounded probabilistic algorithms\n                      , in Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Los Alamitos, NV, 1999, IEEE Computer Society, Piscataway, NJ, pp. 188\u2013199.","DOI":"10.1109\/CCC.1999.766276"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"A. Cohen and A. Wigderson,\n                      Dispersers, deterministic amplification, and weak random sources\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Chapel Hill, NC, 1989, IEEE Press, Piscataway, NJ, pp. 14\u201319.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90022-T"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Pseudorandomness, Lecture Notes in Comput. Sci., Vol. 1853, Springer, Berlin, 2000, 687\u20137041795928","DOI":"10.1007\/3-540-45022-X_58"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Avi Wigderson, Derandomization that is rarely wrong from short advice that is typically good, Lecture Notes in Comput. Sci., Vol. 2483, Springer, Berlin, 2002, 209\u20132232004m:68091","DOI":"10.1007\/3-540-45726-7_17"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad,\n                      Almost optimal lower bounds for small depth circuits\n                      , in Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, 1986, ACM, New York, pp. 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80012-2"},{"key":"R19","unstructured":"T. Hartman and R. Raz,\n                      On the distribution of the number of roots of polynomials and explicit logspace extractors\n                      , in Proceedings of the 4th International Workshop on Randomization and Approximation Techniques in Computer Science, Geneva, Switzerland, 2000, pp. 3\u201322."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, N. Nisan, and A. Wigderson,\n                      Pseudorandomness for network algorithms\n                      , in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, Montreal, QC, 1994, ACM, New York, pp. 356\u2013364.","DOI":"10.1145\/195058.195190"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Avi Wigderson, P=BPP if E requires exponential circuits: derandomizing the XOR lemma, ACM, New York, 1999, 220\u20132291715634","DOI":"10.1145\/258533.258590"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and D. Zuckerman,\n                      How to recycle random bits\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, NC, 1989, IEEE Press, Piscataway, NJ, pp. 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1763"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"R27","first-page":"191","volume":"28","author":"Karp R.","year":"1982","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"R28","unstructured":"R. Karp, N. Pippenger, and M. Sipser,\n                      A time randomness tradeoff\n                      , in Proceedings of the AMS Conference on Probabilistic Computational Complexity, Durham, NH, 1985."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00127-1"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8196-9"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"R34","first-page":"67","author":"Shaltiel Ronen","year":"2002","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90035-9"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273915"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel, Christopher Umans, Simple extractors for all min\u2010entropies and a new pseudo\u2010random generator, IEEE Computer Soc., Los Alamitos, CA, 2001, 648\u20136571948754","DOI":"10.1109\/SFCS.2001.959941"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"R. Santhanam and D. van Melkebeek,\n                      Holographic proofs and derandomization\n                      , in Proceedings of the 18th Annual IEEE Conference on Computational Complexity, Aarhus, Denmark, 2003, IEEE Press, Piscataway, NJ, pp. 269\u2013283.","DOI":"10.1109\/CCC.2003.1214427"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58575-3"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"Andrew Yao, Theory and applications of trapdoor functions, IEEE, New York, 1982, 80\u201391780384","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703438629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:20Z","timestamp":1787336240000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703438629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539703438629"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703438629","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}