{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:53Z","timestamp":1750219793131,"version":"3.41.0"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T00:00:00Z","timestamp":1681948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1741615, CCF-2127597"],"award-info":[{"award-number":["CCF-1741615, CCF-2127597"]}]},{"name":"Google Faculty Research Award, an IBM Fellowship, and a Miller Research Fellowship"},{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["1262\/18"],"award-info":[{"award-number":["1262\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Technion Hiroshi Fujiwara cyber center, and by the European Union","award":["101041208"],"award-info":[{"award-number":["101041208"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["819702"],"award-info":[{"award-number":["819702"]}]},{"name":"National Science Foundation","award":["CCF-1445755, CCF-1900460"],"award-info":[{"award-number":["CCF-1445755, CCF-1900460"]}]},{"DOI":"10.13039\/501100003977","name":"the Israel Science Foundation","doi-asserted-by":"crossref","award":["2893\/22"],"award-info":[{"award-number":["2893\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012443","name":"BIU Center for Research in Applied Cryptography and Cyber Security","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012443","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,8,31]]},"abstract":"<jats:p>\n            The\n            <jats:bold>Exponential-Time Hypothesis (ETH)<\/jats:bold>\n            is a strengthening of the \ud835\udcab \u2260 \ud835\udca9\ud835\udcab conjecture, stating that 3-\n            <jats:monospace>SAT<\/jats:monospace>\n            on\n            <jats:italic>n<\/jats:italic>\n            variables cannot be solved in (uniform) time 2\n            <jats:sup>\n              \u03b5\u010b\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            , for some \u03b5 &gt; 0. In recent years, analogous hypotheses that are \u201cexponentially strong\u201d forms of other classical complexity conjectures (such as \ud835\udca9\ud835\udcab\u2288 \u212c\ud835\udcab\ud835\udcab or\n            <jats:italic>co<\/jats:italic>\n            \ud835\udca9\ud835\udcab\u2288\ud835\udca9\ud835\udcab) have also been introduced and have become widely influential.\n          <\/jats:p>\n          <jats:p>\n            In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely related questions of\n            <jats:italic>derandomization and circuit lower bounds<\/jats:italic>\n            . We show that even relatively mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that:\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(1)<\/jats:label>\n                <jats:p>\n                  The\n                  <jats:bold>Randomized Exponential-Time Hypothesis (rETH)<\/jats:bold>\n                  implies that \u212c\ud835\udcab\ud835\udcab can be simulated on \u201caverage-case\u201d in\n                  <jats:italic>deterministic (nearly-)polynomial-time<\/jats:italic>\n                  (i.e., in time 2\n                  <jats:sup>\n                    \u00d5(log(\n                    <jats:italic>n<\/jats:italic>\n                    ))\n                  <\/jats:sup>\n                  = n\n                  <jats:sup>\n                    loglog(\n                    <jats:italic>n<\/jats:italic>\n                    )\n                    <jats:sup>O(1)<\/jats:sup>\n                  <\/jats:sup>\n                  ). The derandomization relies on a conditional construction of a pseudorandom generator with\n                  <jats:italic>near-exponential stretch<\/jats:italic>\n                  (i.e., with seed length \u00d5(log (\n                  <jats:italic>n<\/jats:italic>\n                  ))); this significantly improves the state-of-the-art in uniform \u201chardness-to-randomness\u201d results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(2)<\/jats:label>\n                <jats:p>\n                  The\n                  <jats:bold>Non-Deterministic Exponential-Time Hypothesis (NETH)<\/jats:bold>\n                  implies that derandomization of \u212c\ud835\udcab\ud835\udcab is\n                  <jats:italic>completely equivalent<\/jats:italic>\n                  to circuit lower bounds against \u2130, and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a\n                  <jats:italic>very weak version of<\/jats:italic>\n                  NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            Last, we show that\n            <jats:italic>disproving<\/jats:italic>\n            certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if\n            <jats:monospace>CircuitSAT<\/jats:monospace>\n            for circuits over\n            <jats:italic>n<\/jats:italic>\n            bits of size poly(n) can be solved by\n            <jats:italic>probabilistic algorithms<\/jats:italic>\n            in time 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n              \/polylog(n)\n            <\/jats:sup>\n            , then \u212c\ud835\udcab\u2130 does not have circuits of quasilinear size.\n          <\/jats:p>","DOI":"10.1145\/3593581","type":"journal-article","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T12:19:23Z","timestamp":1681993163000},"page":"1-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6084-4729","authenticated-orcid":false,"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Miller Institute for Basic Research in Science at University of California, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9693-9244","authenticated-orcid":false,"given":"Roei","family":"Tell","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study and DIMACS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8599-2472","authenticated-orcid":false,"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_3_2_2","DOI":"10.1109\/SFCS.1978.37"},{"doi-asserted-by":"publisher","key":"e_1_3_3_3_2","DOI":"10.1017\/CBO9780511804090"},{"doi-asserted-by":"publisher","key":"e_1_3_3_4_2","DOI":"10.1007\/BF01275486"},{"doi-asserted-by":"publisher","key":"e_1_3_3_5_2","DOI":"10.1145\/2488608.2488681"},{"doi-asserted-by":"publisher","key":"e_1_3_3_6_2","DOI":"10.1137\/0210008"},{"doi-asserted-by":"publisher","key":"e_1_3_3_7_2","DOI":"10.1145\/301250.301444"},{"doi-asserted-by":"publisher","key":"e_1_3_3_8_2","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_3_3_9_2","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Carmosino Marco L.","year":"2018","unstructured":"Marco L. Carmosino, Russell Impagliazzo, and Manuel Sabin. 2018. Fine-grained derandomization: From problem-centric to resource-centric complexity. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)."},{"doi-asserted-by":"publisher","key":"e_1_3_3_10_2","DOI":"10.1109\/FOCS.2019.00079"},{"key":"e_1_3_3_11_2","first-page":"30:1\u201330:21","volume-title":"Proceedings of the 34th Annual IEEE Conference on Computational Complexity (CCC)","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. 2019. Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. In Proceedings of the 34th Annual IEEE Conference on Computational Complexity (CCC). 30:1\u201330:21."},{"doi-asserted-by":"publisher","key":"e_1_3_3_12_2","DOI":"10.1145\/3357713.3384279"},{"doi-asserted-by":"publisher","key":"e_1_3_3_13_2","DOI":"10.1109\/FOCS54457.2022.00048"},{"key":"e_1_3_3_14_2","first-page":"125","volume-title":"Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen and Roei Tell. 2021. Hardness vs. randomness, revised: Uniform, non-black-box, and instance-wise. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 125\u2013136."},{"key":"e_1_3_3_15_2","first-page":"19:1\u201319:43","volume-title":"Proceedings of the 34th Annual IEEE Conference on Computational Complexity (CCC)","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen and R. Ryan Williams. 2019. Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. In Proceedings of the 34th Annual IEEE Conference on Computational Complexity (CCC). 19:1\u201319:43."},{"issue":"4","key":"e_1_3_3_16_2","article-title":"Exponential time complexity of the permanent and the Tutte polynomial","volume":"10","author":"Dell Holger","year":"2014","unstructured":"Holger Dell, Thore Husfeldt, D\u00e1niel Marx, Nina Taslaman, and Martin Wahl\u00e9n. 2014. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algor. 10, 4 (2014).","journal-title":"ACM Trans. Algor."},{"doi-asserted-by":"publisher","key":"e_1_3_3_17_2","DOI":"10.1016\/j.jcss.2008.07.006"},{"doi-asserted-by":"publisher","key":"e_1_3_3_18_2","DOI":"10.1109\/CCC.2009.21"},{"key":"e_1_3_3_19_2","first-page":"429","article-title":"On completeness and soundness in interactive proof systems","volume":"5","author":"F\u00fcrer Martin","year":"1989","unstructured":"Martin F\u00fcrer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos. 1989. On completeness and soundness in interactive proof systems. Adv. Comput. Res. 5 (1989), 429\u2013442.","journal-title":"Adv. Comput. Res."},{"doi-asserted-by":"publisher","key":"e_1_3_3_20_2","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_3_3_21_2","first-page":"191","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay Randomness and Computation","author":"Goldreich Oded","year":"2011","unstructured":"Oded Goldreich. 2011. In a world of P=BPP. In Studies in Complexity and Cryptography. Miscellanea on the Interplay Randomness and Computation. 191\u2013232."},{"doi-asserted-by":"publisher","key":"e_1_3_3_22_2","DOI":"10.1145\/73007.73010"},{"doi-asserted-by":"publisher","key":"e_1_3_3_23_2","DOI":"10.1145\/2799645"},{"key":"e_1_3_3_24_2","first-page":"130","article-title":"Worst-case to average-case reductions for subclasses of P","volume":"26","author":"Goldreich Oded","year":"2017","unstructured":"Oded Goldreich and Guy N. Rothblum. 2017. Worst-case to average-case reductions for subclasses of P. Electron. Colloq. Computat. Complex. 26 (2017), 130.","journal-title":"Electron. Colloq. Computat. Complex."},{"doi-asserted-by":"publisher","key":"e_1_3_3_25_2","DOI":"10.5555\/646798.705312"},{"doi-asserted-by":"publisher","key":"e_1_3_3_26_2","DOI":"10.1145\/1538902.1538904"},{"doi-asserted-by":"publisher","key":"e_1_3_3_27_2","DOI":"10.1007\/s00037-003-0178-7"},{"doi-asserted-by":"publisher","key":"e_1_3_3_28_2","DOI":"10.1007\/978-3-540-85363-3_37"},{"doi-asserted-by":"publisher","key":"e_1_3_3_29_2","DOI":"10.1145\/2539126.2539130"},{"doi-asserted-by":"publisher","key":"e_1_3_3_30_2","DOI":"10.1002\/rsa.10095"},{"doi-asserted-by":"publisher","key":"e_1_3_3_31_2","DOI":"10.1016\/S0022-0000(02)00024-7"},{"doi-asserted-by":"publisher","key":"e_1_3_3_32_2","DOI":"10.1006\/jcss.2000.1727"},{"doi-asserted-by":"publisher","key":"e_1_3_3_33_2","DOI":"10.1006\/jcss.2001.1774"},{"doi-asserted-by":"publisher","key":"e_1_3_3_34_2","DOI":"10.1109\/SFCS.1998.743524"},{"key":"e_1_3_3_35_2","first-page":"220","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC)","author":"Impagliazzo Russell","year":"1999","unstructured":"Russell Impagliazzo and Avi Wigderson. 1999. \\({\\rm P}={\\rm BPP}\\) if \\({\\rm E}\\) requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC). 220\u2013229."},{"doi-asserted-by":"crossref","unstructured":"Valentine Kabanets. 2001. Easiness assumptions and hardness tests: Trading time for zero error. Vol. 63. 236\u2013252. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000001917635.","key":"e_1_3_3_36_2","DOI":"10.1006\/jcss.2001.1763"},{"doi-asserted-by":"publisher","key":"e_1_3_3_37_2","DOI":"10.1016\/S0019-9958(82)90382-5"},{"doi-asserted-by":"publisher","key":"e_1_3_3_38_2","DOI":"10.1109\/CCC.2013.18"},{"doi-asserted-by":"publisher","key":"e_1_3_3_39_2","DOI":"10.1007\/s00037-013-0069-5"},{"key":"e_1_3_3_40_2","volume-title":"Proceedings of the 37th Annual IEEE Conference on Computational Complexity (CCC)","author":"Liu Yanyi","year":"2022","unstructured":"Yanyi Liu and Rafael Pass. 2022. Characterizing derandomization through fine-grained hardness of Levin-Kolmogorov complexity. In Proceedings of the 37th Annual IEEE Conference on Computational Complexity (CCC)."},{"issue":"105","key":"e_1_3_3_41_2","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. Eur. Assoc. Theoret. Comput. Sci.105 (2011), 41\u201371.","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci."},{"doi-asserted-by":"publisher","key":"e_1_3_3_42_2","DOI":"10.1007\/s00037-001-8196-9"},{"doi-asserted-by":"publisher","key":"e_1_3_3_43_2","DOI":"10.1145\/146585.146605"},{"doi-asserted-by":"publisher","key":"e_1_3_3_44_2","DOI":"10.1145\/3188745.3188910"},{"doi-asserted-by":"publisher","key":"e_1_3_3_45_2","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_3_46_2","first-page":"117","article-title":"Algorithms versus circuit lower bounds","volume":"20","author":"Oliveira Igor C.","year":"2013","unstructured":"Igor C. Oliveira. 2013. Algorithms versus circuit lower bounds. Electron. Colloq. Computat. Complex. 20 (2013), 117.","journal-title":"Electron. Colloq. Computat. Complex."},{"key":"e_1_3_3_47_2","volume-title":"Proceedings of the 32nd Annual IEEE Conference on Computational Complexity (CCC)","volume":"79","author":"Oliveira Igor C.","year":"2017","unstructured":"Igor C. Oliveira and Rahul Santhanam. 2017. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Proceedings of the 32nd Annual IEEE Conference on Computational Complexity (CCC). Vol. 79.."},{"doi-asserted-by":"publisher","key":"e_1_3_3_48_2","DOI":"10.1145\/322123.322138"},{"doi-asserted-by":"publisher","key":"e_1_3_3_49_2","DOI":"10.1137\/070702680"},{"doi-asserted-by":"publisher","key":"e_1_3_3_50_2","DOI":"10.1109\/CCC.2013.40"},{"doi-asserted-by":"publisher","key":"e_1_3_3_51_2","DOI":"10.1145\/1059513.1059516"},{"doi-asserted-by":"publisher","key":"e_1_3_3_52_2","DOI":"10.1145\/1250790.1250854"},{"doi-asserted-by":"publisher","key":"e_1_3_3_53_2","DOI":"10.1145\/146585.146609"},{"doi-asserted-by":"publisher","key":"e_1_3_3_54_2","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"doi-asserted-by":"publisher","key":"e_1_3_3_55_2","DOI":"10.1006\/jcss.2000.1730"},{"doi-asserted-by":"publisher","key":"e_1_3_3_56_2","DOI":"10.1016\/j.ipl.2019.105841"},{"doi-asserted-by":"publisher","key":"e_1_3_3_57_2","DOI":"10.1007\/s00037-007-0233-x"},{"doi-asserted-by":"publisher","key":"e_1_3_3_58_2","DOI":"10.1016\/S0022-0000(03)00046-1"},{"doi-asserted-by":"publisher","key":"e_1_3_3_59_2","DOI":"10.5555\/2464831"},{"doi-asserted-by":"publisher","key":"e_1_3_3_60_2","DOI":"10.1137\/10080703X"},{"key":"e_1_3_3_61_2","first-page":"659","volume-title":"Proceedings of the International Congress of Mathematicians (ICM)","author":"Williams Ryan","year":"2014","unstructured":"Ryan Williams. 2014. Algorithms for circuits and circuits for algorithms: Connecting the tractable and intractable. In Proceedings of the International Congress of Mathematicians (ICM). 659\u2013682."},{"key":"e_1_3_3_62_2","volume-title":"Proceedings of the 31st Annual IEEE Conference on Computational Complexity (CCC)","author":"Williams Richard Ryan","year":"2016","unstructured":"Richard Ryan Williams. 2016. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proceedings of the 31st Annual IEEE Conference on Computational Complexity (CCC)."},{"key":"e_1_3_3_63_2","first-page":"17","volume-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation","volume":"43","author":"Williams Virginia V.","year":"2015","unstructured":"Virginia V. Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Vol. 43. 17\u201329."},{"unstructured":"Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. Retrieved from https:\/\/people.csail.mit.edu\/virgi\/eccentri.pdf.","key":"e_1_3_3_64_2"},{"key":"e_1_3_3_65_2","series-title":"(Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization\u2014Eureka, You Shrink!","author":"Woeginger Gerhard J.","year":"2003","unstructured":"Gerhard J. Woeginger. 2003. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization\u2014Eureka, You Shrink!(Lecture Notes in Computer Science, Vol. 2570). Springer, Berlin, 185\u2013207."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593581","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3593581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:01Z","timestamp":1750178281000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,20]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1145\/3593581"],"URL":"https:\/\/doi.org\/10.1145\/3593581","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,4,20]]},"assertion":[{"value":"2021-04-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}