{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T03:40:11Z","timestamp":1773546011992,"version":"3.50.1"},"reference-count":103,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T00:00:00Z","timestamp":1528848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2018,6,13]]},"abstract":"<jats:p>Recent advances in nonequilibrium statistical mechanics have led to a deeper understanding of the thermodynamic cost of computation than that put forth by Landauer and then studied extensively in the computational complexity community. In particular, Landauer's work led to a focus on the number of bit erasures in a computation, due to its relation to the change in entropy between input and output. However new advances in physics|which have been experimentally con rmed|mean we can now calculate additional thermodynamic costs beyond merely the change in entropy between input and output. As a consequence, we now understand that while logically reversible computing can have some thermodynamic bene ts, it is far from the end of the story. The purpose of this paper is to highlight new open questions in computational complexity raised by consideration of these new thermodynamic costs. Beyond leading to a revised viewpoint on the bene ts of logical reversibility, these questions touch on randomized algorithms, average-case complexity, the thermodynamic cost of error correcting codes, and noisy\/inexact\/approximate computation.<\/jats:p>","DOI":"10.1145\/3232679.3232689","type":"journal-article","created":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T13:02:37Z","timestamp":1528894957000},"page":"33-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Beyond Number of Bit Erasures"],"prefix":"10.1145","volume":"49","author":[{"given":"Joshua A.","family":"Grochow","sequence":"first","affiliation":[{"name":"University of Colorado Boulder, Boulder, CO, USA"}]},{"given":"David H.","family":"Wolpert","sequence":"additional","affiliation":[{"name":"University of Colorado Boulder, Boulder, CO, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055484"},{"key":"e_1_2_1_2_1","volume-title":"Sustaining Moore's Law through inexactness. arXiv:1705.01497 {cs.CC}","author":"Augustine John","year":"2017","unstructured":"John Augustine , Krishna Palem , and Parishkrati. Sustaining Moore's Law through inexactness. arXiv:1705.01497 {cs.CC} , 2017 . John Augustine, Krishna Palem, and Parishkrati. Sustaining Moore's Law through inexactness. arXiv:1705.01497 {cs.CC}, 2017."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806620"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/154032.154033"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90019-F"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"issue":"12","key":"e_1_2_1_7_1","first-page":"940","article-title":"The thermodynamics of computation|a review","volume":"21","author":"Bennett Charles H","year":"1982","unstructured":"Charles H Bennett . The thermodynamics of computation|a review . Internat. J. Theoret. Phys. , 21 ( 12 ):905{ 940 , 1982 . Charles H Bennett. The thermodynamics of computation|a review. Internat. J. Theoret. Phys., 21(12):905{940, 1982.","journal-title":"Internat. J. Theoret. Phys."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218053"},{"issue":"3","key":"e_1_2_1_9_1","first-page":"510","article-title":"Notes on Landauer's principle, reversible computation, and Maxwell's Demon","volume":"34","author":"Bennett Charles H.","year":"2003","unstructured":"Charles H. Bennett . Notes on Landauer's principle, reversible computation, and Maxwell's Demon . Studies Hist. Phil. Sci. B , 34 ( 3 ):501{ 510 , 2003 . Charles H. Bennett. Notes on Landauer's principle, reversible computation, and Maxwell's Demon. Studies Hist. Phil. Sci. B, 34(3):501{510, 2003.","journal-title":"Studies Hist. Phil. Sci. B"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-012-9124-7"},{"key":"e_1_2_1_13_1","volume-title":"Crutch eld. Above and beyond the Landauer bound: thermodynamics of modularity. arXiv:1708.03030","author":"Boyd Alexander B.","year":"2017","unstructured":"Alexander B. Boyd , Dibyendu Mandal , and James P . Crutch eld. Above and beyond the Landauer bound: thermodynamics of modularity. arXiv:1708.03030 , 2017 . Alexander B. Boyd, Dibyendu Mandal, and James P. Crutch eld. Above and beyond the Landauer bound: thermodynamics of modularity. arXiv:1708.03030, 2017."},{"key":"e_1_2_1_14_1","volume-title":"Understanding and designing energy efficiency programs for data centers","author":"Mark Bram","year":"2012","unstructured":"Mark Bram tt, Allison Bard , Robert Huang , and Maureen McNamara . Understanding and designing energy efficiency programs for data centers , 2012 . URL : https:\/\/www.energystar.gov\/buildings\/tools-and-resources\/ understanding-and-designing-energy-efficiency-programs-data-centers. Mark Bram tt, Allison Bard, Robert Huang, and Maureen McNamara. Understanding and designing energy efficiency programs for data centers, 2012. URL: https:\/\/www.energystar.gov\/buildings\/tools-and-resources\/ understanding-and-designing-energy-efficiency-programs-data-centers."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1721463"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3057866"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684114"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/34\/35\/308"},{"issue":"3","key":"e_1_2_1_19_1","first-page":"101","article-title":"A simple derivation of Crooks relation","volume":"16","author":"Janna Farid Chejne","year":"2013","unstructured":"Farid Chejne Janna , Fadl Moukalled , and Carlos Andr\u00e9s G\u00f2mez . A simple derivation of Crooks relation . Internat. J. Thermodyn. , 16 ( 3 ):97{ 101 , 2013 . Farid Chejne Janna, Fadl Moukalled, and Carlos Andr\u00e9s G\u00f2mez. A simple derivation of Crooks relation. Internat. J. Thermodyn., 16(3):97{101, 2013.","journal-title":"Internat. J. Thermodyn."},{"key":"e_1_2_1_20_1","volume-title":"Conf. Board of the Mathematical Sciences, Washington, DC; by the Amer. Math. Soc.","author":"Chung Fan","year":"2006","unstructured":"Fan Chung and Linyuan Lu . Complex graphs and networks, volume 107 of CBMS Regional Conference Series in Mathematics . Conf. Board of the Mathematical Sciences, Washington, DC; by the Amer. Math. Soc. , Providence, RI , 2006 . Fan Chung and Linyuan Lu. Complex graphs and networks, volume 107 of CBMS Regional Conference Series in Mathematics. Conf. Board of the Mathematical Sciences, Washington, DC; by the Amer. Math. Soc., Providence, RI, 2006."},{"key":"e_1_2_1_21_1","volume-title":"Linear programming","author":"Chv\u00e0tal Va\u0161ek","year":"1983","unstructured":"Va\u0161ek Chv\u00e0tal . Linear programming . A Series of Books in the Mathematical Sciences. W. H. Freeman and Company , New York, 1983 . Va\u0161ek Chv\u00e0tal. Linear programming. A Series of Books in the Mathematical Sciences. W. H. Freeman and Company, New York, 1983."},{"key":"e_1_2_1_22_1","volume-title":"The Register","author":"Clark Jack","year":"2013","unstructured":"Jack Clark . IT now 10 percent of world's electricity consumption, report nds . The Register , August 2013 . URL: https:\/\/www.theregister.co.uk\/2013\/08\/16\/it_electricity_use_ worse_than_you_thought\/. Jack Clark. IT now 10 percent of world's electricity consumption, report nds. The Register, August 2013. URL: https:\/\/www.theregister.co.uk\/2013\/08\/16\/it_electricity_use_ worse_than_you_thought\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(99)00225-6"},{"key":"e_1_2_1_24_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Cli ord Stein . Introduction to algorithms . MIT Press , Cambridge, MA , third edition, 2009 . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cli ord Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80017-4"},{"key":"e_1_2_1_26_1","volume-title":"Nonequilibrium measurements of free energy di erences for microscopically reversible Markovian systems. J. Stat. Phys., 90(5{6):1481{1487","author":"Crooks Gavin E.","year":"1998","unstructured":"Gavin E. Crooks . Nonequilibrium measurements of free energy di erences for microscopically reversible Markovian systems. J. Stat. Phys., 90(5{6):1481{1487 , 1998 . Gavin E. Crooks. Nonequilibrium measurements of free energy di erences for microscopically reversible Markovian systems. J. Stat. Phys., 90(5{6):1481{1487, 1998."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.60.2721"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/87252.88081"},{"issue":"4","key":"e_1_2_1_29_1","first-page":"041003","article-title":"De ner and Christopher Jarzynski. Information processing and the second law of thermodynamics: An inclusive, Hamiltonian approach","volume":"3","author":"Sebastian","year":"2013","unstructured":"Sebastian De ner and Christopher Jarzynski. Information processing and the second law of thermodynamics: An inclusive, Hamiltonian approach . Phys. Rev. X , 3 ( 4 ): 041003 , 2013 . Sebastian De ner and Christopher Jarzynski. Information processing and the second law of thermodynamics: An inclusive, Hamiltonian approach. Phys. Rev. X, 3(4):041003, 2013.","journal-title":"Phys. Rev. X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840756"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/pamm.201610407"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Comput","first-page":"286","volume-title":"Jo ao Marques-Silva and Karem A","author":"Een Niklas","unstructured":"Niklas Een , Alan Mishchenko , and Niklas S\u00f6rensson . Applying logic synthesis for speeding up SAT . In Jo ao Marques-Silva and Karem A . Sakallah, editors, SAT '07, volume 4501 of Lecture Notes in Comput . Sci ., pages 272{ 286 . Springer, Berlin, 2007. Niklas Een, Alan Mishchenko, and Niklas S\u00f6rensson. Applying logic synthesis for speeding up SAT. In Jo ao Marques-Silva and Karem A. Sakallah, editors, SAT '07, volume 4501 of Lecture Notes in Comput. Sci., pages 272{286. Springer, Berlin, 2007."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.011143"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/95\/40004"},{"key":"e_1_2_1_35_1","volume-title":"Report to congress on server and data center energy efficiency public law","author":"Fanara Andrew","year":"2007","unstructured":"Andrew Fanara , Jill Abelson , Ann Bailey , Kim Crossman , Robin Shudak , Alexandra Sullivan , Maria Vargas , and Mike Zatz . Report to congress on server and data center energy efficiency public law 109-431, August 2007 . URL : https:\/\/www.energystar.gov\/buildings\/tools-and-resources\/ report-congress-server-and-data-center-energy-efficiency-opportunities. Andrew Fanara, Jill Abelson, Ann Bailey, Kim Crossman, Robin Shudak, Alexandra Sullivan, Maria Vargas, and Mike Zatz. Report to congress on server and data center energy efficiency public law 109-431, August 2007. URL: https:\/\/www.energystar.gov\/buildings\/tools-and-resources\/ report-congress-server-and-data-center-energy-efficiency-opportunities."},{"key":"e_1_2_1_36_1","first-page":"182","volume-title":"Unconventional models of computation (Auckland","author":"Frank Michael","year":"1998","unstructured":"Michael Frank , Tom Knight , and Norm Margolus . Reversibility in optimally scalable computer architectures . In Unconventional models of computation (Auckland , 1998 ), Springer Ser . Discrete Math. Theor. Comput. Sci., pages 165{ 182 . Springer, Singapore, 1998. Michael Frank, Tom Knight, and Norm Margolus. Reversibility in optimally scalable computer architectures. In Unconventional models of computation (Auckland, 1998), Springer Ser. Discrete Math. Theor. Comput. Sci., pages 165{182. Springer, Singapore, 1998."},{"issue":"3","key":"e_1_2_1_37_1","first-page":"253","article-title":"Conservative logic","volume":"21","author":"Fredkin Edward","year":"1982","unstructured":"Edward Fredkin and Tommaso To oli. Conservative logic . Internat. J. Theoret. Phys. , 21 ( 3 ):219{ 253 , 1982 . Edward Fredkin and Tommaso To oli. Conservative logic. Internat. J. Theoret. Phys., 21(3):219{253, 1982.","journal-title":"Internat. J. Theoret. Phys."},{"issue":"095003","key":"e_1_2_1_38_1","article-title":"Introducing one-shot work into uctuation relations","volume":"17","author":"Halpern Nicole Yunger","year":"2015","unstructured":"Nicole Yunger Halpern , Andrew J. P. Garner , Oscar C. O. Dahlsten , and Vlatko Vedral . Introducing one-shot work into uctuation relations . New J. Phys. , 17 ( 095003 ), 2015 . Focus Issue on Quantum Thermodynamics. Preprint available as arXiv:1409.3878 {cond-mat.statmech}. Nicole Yunger Halpern, Andrew J. P. Garner, Oscar C. O. Dahlsten, and Vlatko Vedral. Introducing one-shot work into uctuation relations. New J. Phys., 17(095003), 2015. Focus Issue on Quantum Thermodynamics. Preprint available as arXiv:1409.3878 {cond-mat.statmech}.","journal-title":"New J. Phys."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2009.12.042"},{"issue":"3","key":"e_1_2_1_40_1","first-page":"031015","article-title":"Thermodynamics with continuous information ow","volume":"4","author":"Horowitz Jordan M","year":"2014","unstructured":"Jordan M Horowitz and Massimiliano Esposito . Thermodynamics with continuous information ow . Phys. Rev. X , 4 ( 3 ): 031015 , 2014 . Jordan M Horowitz and Massimiliano Esposito. Thermodynamics with continuous information ow. Phys. Rev. X, 4(3):031015, 2014.","journal-title":"Phys. Rev. X"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.2690"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"issue":"5","key":"e_1_2_1_43_1","first-page":"1096","article-title":"A polynomial algorithm in linear programming","volume":"244","author":"Kha\u010dijan L. G.","year":"1979","unstructured":"L. G. Kha\u010dijan . A polynomial algorithm in linear programming . Dokl. Akad. Nauk SSSR , 244 ( 5 ):1093{ 1096 , 1979 . L. G. Kha\u010dijan. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR, 244(5):1093{1096, 1979.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_44_1","volume-title":"Springer","author":"Kol Gillat","year":"2014","unstructured":"Gillat Kol , Shay Moran , Amir Shpilka , and Amir Yehudayo . Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Automata, Languages, and Programming (ICALP 2014), pages 701{712 . Springer , 2014 . Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayo . Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Automata, Languages, and Programming (ICALP 2014), pages 701{712. Springer, 2014."},{"key":"e_1_2_1_45_1","volume-title":"Dependence of dissipation on the initial distribution over states. J. Stat. Mech., page 083202","author":"Kolchinsky Artemy","year":"2017","unstructured":"Artemy Kolchinsky and David H. Wolpert . Dependence of dissipation on the initial distribution over states. J. Stat. Mech., page 083202 , 2017 . Preprint available as arXiv:1607.00956 {cond-mat.stat-mech}. Artemy Kolchinsky and David H. Wolpert. Dependence of dissipation on the initial distribution over states. J. Stat. Mech., page 083202, 2017. Preprint available as arXiv:1607.00956 {cond-mat.stat-mech}."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742482"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.881299"},{"issue":"5270","key":"e_1_2_1_49_1","first-page":"1918","article-title":"Minimal energy requirements in communication","volume":"272","author":"Landauer Rolf","year":"1914","unstructured":"Rolf Landauer . Minimal energy requirements in communication . Science , 272 ( 5270 ): 1914 { 1918 , 1996. Rolf Landauer. Minimal energy requirements in communication. Science, 272(5270):1914{ 1918, 1996.","journal-title":"Science"},{"issue":"4","key":"e_1_2_1_50_1","first-page":"193","article-title":"The physical nature of information","volume":"217","author":"Landauer Rolf","year":"1996","unstructured":"Rolf Landauer . The physical nature of information . Physics Letters A , 217 ( 4 ):188{ 193 , 1996 . Rolf Landauer. The physical nature of information. Physics Letters A, 217(4):188{193, 1996.","journal-title":"Physics Letters A"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1672"},{"key":"e_1_2_1_52_1","series-title":"Lecture Notes in Comput","first-page":"303","volume-title":"Integer programming and combinatorial optimization (Utrecht","author":"Lasserre Jean B.","year":"2001","unstructured":"Jean B. Lasserre . An explicit exact SDP relaxation for nonlinear 0-1 programs . In Integer programming and combinatorial optimization (Utrecht , 2001 ), volume 2081 of Lecture Notes in Comput . Sci ., pages 293{ 303 . Springer, Berlin, 2001. Jean B. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1 programs. In Integer programming and combinatorial optimization (Utrecht, 2001), volume 2081 of Lecture Notes in Comput. Sci., pages 293{303. Springer, Berlin, 2001."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_2_1_54_1","series-title":"Imperial College Press Optimization Series","volume-title":"positive polynomials and their applications","author":"Lasserre Jean Bernard","year":"2010","unstructured":"Jean Bernard Lasserre . Moments , positive polynomials and their applications , volume 1 of Imperial College Press Optimization Series . Imperial College Press , London , 2010 . Jean Bernard Lasserre. Moments, positive polynomials and their applications, volume 1 of Imperial College Press Optimization Series. Imperial College Press, London, 2010."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226"},{"issue":"3","key":"e_1_2_1_56_1","first-page":"35","article-title":"Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory","volume":"10","author":"Levin L. A.","year":"1974","unstructured":"L. A. Levin . Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory . Problemy Pereda\u010di Informacii , 10 ( 3 ):30{ 35 , 1974 . L. A. Levin. Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory. Problemy Pereda\u010di Informacii, 10(3):30{35, 1974.","journal-title":"Problemy Pereda\u010di Informacii"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219046"},{"key":"e_1_2_1_59_1","volume-title":"Doing Moore with less { leapfrogging Moore's Law with inexactness for supercomputing. arXiv:1610.02606 {cs.OH}","author":"Sven Ley","year":"2016","unstructured":"Sven Ley er, Stefan M. Wild , Mike Fagan , Marc Snir , Krishna Palem , Kazutomo Yoshii , and Hal Finkel . Doing Moore with less { leapfrogging Moore's Law with inexactness for supercomputing. arXiv:1610.02606 {cs.OH} , 2016 . Sven Ley er, Stefan M. Wild, Mike Fagan, Marc Snir, Krishna Palem, Kazutomo Yoshii, and Hal Finkel. Doing Moore with less { leapfrogging Moore's Law with inexactness for supercomputing. arXiv:1610.02606 {cs.OH}, 2016."},{"key":"e_1_2_1_60_1","first-page":"176","volume-title":"Proceedings of the Fourth Workshop on Physics and Computation, PhysComp96","author":"Li Ming","unstructured":"Ming Li , John Tromp , and Paul Vitanyi . Reversible simulation of irreversible computation . In Proceedings of the Fourth Workshop on Physics and Computation, PhysComp96 , pages 168{ 176 . Elsevier, 1998. URL: http:\/\/dl.acm.org\/citation.cfm?id=300494.300821. Ming Li, John Tromp, and Paul Vitanyi. Reversible simulation of irreversible computation. In Proceedings of the Fourth Workshop on Physics and Computation, PhysComp96, pages 168{176. Elsevier, 1998. URL: http:\/\/dl.acm.org\/citation.cfm?id=300494.300821."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-2789(98)00052-9"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00008-6"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_64_1","volume-title":"Morgan Kaufmann","author":"Lynch Nancy A.","year":"1996","unstructured":"Nancy A. Lynch . Distributed algorithms . Morgan Kaufmann , San Francisco, CA , 1996 . Nancy A. Lynch. Distributed algorithms. Morgan Kaufmann, San Francisco, CA, 1996."},{"key":"e_1_2_1_65_1","volume-title":"The New York Times","author":"John Marko","year":"2015","unstructured":"John Marko . A climate-modeling strategy that won't hurt the climate . The New York Times , May 2015 . John Marko . A climate-modeling strategy that won't hurt the climate. The New York Times, May 2015."},{"key":"e_1_2_1_66_1","volume-title":"August","author":"Mills Mark P.","year":"2013","unstructured":"Mark P. Mills . The cloud beings with coal: big data, big networks, big infrastructure, and big power|an overview of the electricity used by the global digital ecosystem , August 2013 . URL: https:\/\/www.tech-pundit.com\/wp-content\/uploads\/2013\/07\/Cloud_ Begins _With_Coal.pdf. Mark P. Mills. The cloud beings with coal: big data, big networks, big infrastructure, and big power|an overview of the electricity used by the global digital ecosystem, August 2013. URL: https:\/\/www.tech-pundit.com\/wp-content\/uploads\/2013\/07\/Cloud_ Begins_With_Coal.pdf."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.041"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_1_70_1","volume-title":"Single-shot quantum thermodynamics|lecture notes. Course materials","author":"M\u00fcller Markus","year":"2014","unstructured":"Markus M\u00fcller and Jakob Scharlau . Single-shot quantum thermodynamics|lecture notes. Course materials available at http:\/\/www.mpmueller.net\/lecture2.html, 2014 . Markus M\u00fcller and Jakob Scharlau. Single-shot quantum thermodynamics|lecture notes. Course materials available at http:\/\/www.mpmueller.net\/lecture2.html, 2014."},{"key":"e_1_2_1_71_1","volume-title":"Pearson","author":"Mulmuley Ketan D.","year":"1993","unstructured":"Ketan D. Mulmuley . Computational geometry: an introduction through randomized algo- rithms . Pearson , 1993 . Ketan D. Mulmuley. Computational geometry: an introduction through randomized algo- rithms. Pearson, 1993."},{"key":"e_1_2_1_72_1","volume-title":"The structure and dynamics of networks. Princeton Studies in Complexity","author":"Newman Mark","year":"2006","unstructured":"Mark Newman , Albert-L\u00e0szl\u00f2 Barab\u00e0i , and Duncan J. Watts . The structure and dynamics of networks. Princeton Studies in Complexity . Princeton University Press , 2006 . Mark Newman, Albert-L\u00e0szl\u00f2 Barab\u00e0i, and Duncan J. Watts. The structure and dynamics of networks. Princeton Studies in Complexity. Princeton University Press, 2006."},{"key":"e_1_2_1_73_1","volume-title":"Number of hidden states needed to physically implement a given conditional distribution. arXiv:1709.00765","author":"Owen Jeremy","year":"2017","unstructured":"Jeremy Owen , Artemy Kolchinsky , and David H. Wolpert . Number of hidden states needed to physically implement a given conditional distribution. arXiv:1709.00765 , 2017 . Jeremy Owen, Artemy Kolchinsky, and David H. Wolpert. Number of hidden states needed to physically implement a given conditional distribution. arXiv:1709.00765, 2017."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/ESSCIRC.2013.6649121"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2014.0118"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510010018916"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1230161216500062"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.062143"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2014\/03\/P03025"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.102.250602"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.109.180602"},{"key":"e_1_2_1_82_1","volume-title":"Theory of linear and integer programming","author":"Schrijver Alexander","year":"1986","unstructured":"Alexander Schrijver . Theory of linear and integer programming . Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd ., Chichester, 1986 . Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1088\/0034-4885\/75\/12\/126001"},{"key":"e_1_2_1_84_1","first-page":"532","volume-title":"Proceedings of a DIMACS Workshop","author":"Selman B.","year":"1993","unstructured":"B. Selman , H. A. Kautz , and B. Cohen . Local search strategies for satis ability testing. In Cliques, Coloring, and Satis ability , Proceedings of a DIMACS Workshop , New Brunswick, New Jersey, USA, October 11{13 , 1993 , pages 521{ 532 , 1993. B. Selman, H. A. Kautz, and B. Cohen. Local search strategies for satis ability testing. In Cliques, Coloring, and Satis ability, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 11{13, 1993, pages 521{532, 1993."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.52.3495"},{"key":"e_1_2_1_87_1","first-page":"516","volume-title":"Proceeding of the 41st Annual International Symposium on Computer Architecture, ISCA '14","author":"Amant Ren\u00e8e St.","year":"2014","unstructured":"Ren\u00e8e St. Amant , Amir Yazdanbakhsh , Jongse Park , Bradley Thwaites , Hadi Esmaeilzadeh , Arjang Hassibi , Luis Ceze , and Doug Burger . General-purpose code acceleration with limitedprecision analog computation . In Proceeding of the 41st Annual International Symposium on Computer Architecture, ISCA '14 , pages 505{ 516 , Piscataway, NJ, USA , 2014 . IEEE Press. URL: http:\/\/dl.acm.org\/citation.cfm?id=2665671.2665746. Ren\u00e8e St. Amant, Amir Yazdanbakhsh, Jongse Park, Bradley Thwaites, Hadi Esmaeilzadeh, Arjang Hassibi, Luis Ceze, and Doug Burger. General-purpose code acceleration with limitedprecision analog computation. In Proceeding of the 41st Annual International Symposium on Computer Architecture, ISCA '14, pages 505{516, Piscataway, NJ, USA, 2014. IEEE Press. URL: http:\/\/dl.acm.org\/citation.cfm?id=2665671.2665746."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.011"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830090402"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2010.11.002"},{"key":"e_1_2_1_91_1","unstructured":"The MathWorks Inc. MATLAB 2017.  The MathWorks Inc. MATLAB 2017."},{"issue":"1","key":"e_1_2_1_92_1","first-page":"172","article-title":"Information-theoretic approach to the study of control systems","volume":"331","author":"Touchette Hugo","year":"2004","unstructured":"Hugo Touchette and Seth Lloyd . Information-theoretic approach to the study of control systems . Physica A , 331 ( 1 ):140{ 172 , 2004 . Hugo Touchette and Seth Lloyd. Information-theoretic approach to the study of control systems. Physica A, 331(1):140{172, 2004.","journal-title":"Physica A"},{"key":"e_1_2_1_93_1","series-title":"Lecture Notes in Comput","first-page":"136","volume-title":"Reversible computation","author":"Tyagi Nirvan","unstructured":"Nirvan Tyagi , Jayson Lynch , and Erik D. Demaine . Toward an energy efficient language and compiler for (partially) reversible algorithms . In Reversible computation , volume 9720 of Lecture Notes in Comput . Sci ., pages 121{ 136 . Springer, {Cham}, 2016. Nirvan Tyagi, Jayson Lynch, and Erik D. Demaine. Toward an energy efficient language and compiler for (partially) reversible algorithms. In Reversible computation, volume 9720 of Lecture Notes in Comput. Sci., pages 121{136. Springer, {Cham}, 2016."},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80041-4"},{"key":"e_1_2_1_95_1","volume-title":"Approximation algorithms","author":"Vazirani Vijay V.","year":"2001","unstructured":"Vijay V. Vazirani . Approximation algorithms . Springer-Verlag , Berlin , 2001 . Vijay V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001."},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062261.1062335"},{"key":"e_1_2_1_97_1","first-page":"98","volume-title":"Automata studies, Annals of mathematics studies, no. 34","author":"von Neumann J.","unstructured":"J. von Neumann . Probabilistic logics and the synthesis of reliable organisms from unreliable components . In Automata studies, Annals of mathematics studies, no. 34 , pages 43{ 98 . Princeton University Press, Princeton, N. J., 1956. J. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata studies, Annals of mathematics studies, no. 34, pages 43{98. Princeton University Press, Princeton, N. J., 1956."},{"key":"e_1_2_1_98_1","volume-title":"Time","author":"Walsh Bryan","year":"2013","unstructured":"Bryan Walsh . The surprisingly large energy footprint of the digital economy . Time , August 2013 . URL: http:\/\/science.time.com\/2013\/08\/14\/ power-drain-the-digital-cloud-is-using-more-energy-than-you-think\/#. Bryan Walsh. The surprisingly large energy footprint of the digital economy. Time, August 2013. URL: http:\/\/science.time.com\/2013\/08\/14\/ power-drain-the-digital-cloud-is-using-more-energy-than-you-think\/#."},{"key":"e_1_2_1_99_1","volume-title":"The Free Encyclopedia","author":"Contributors Wikipedia","year":"2017","unstructured":"Wikipedia Contributors . Comparison of hardware random number generators. Wikipedia , The Free Encyclopedia , 2017 . URL : https:\/\/en.wikipedia.org\/wiki\/Comparison_of_ hardware_random_number_generators. Wikipedia Contributors. Comparison of hardware random number generators. Wikipedia, The Free Encyclopedia, 2017. URL: https:\/\/en.wikipedia.org\/wiki\/Comparison_of_ hardware_random_number_generators."},{"key":"e_1_2_1_100_1","volume-title":"The Mathematicar book. Wolfram Media","year":"1999","unstructured":"StephenWolfram. The Mathematicar book. Wolfram Media , Inc., Champaign, IL; Cambridge University Press , Cambridge, fourth edition, 1999 . StephenWolfram. The Mathematicar book. Wolfram Media, Inc., Champaign, IL; Cambridge University Press, Cambridge, fourth edition, 1999."},{"key":"e_1_2_1_101_1","volume-title":"Extending Landauer's bound from bit erasure to arbitrary computation. arXiv:1508.05319 {cond-mat.stat-mech}","author":"Wolpert David H.","year":"2015","unstructured":"David H. Wolpert . Extending Landauer's bound from bit erasure to arbitrary computation. arXiv:1508.05319 {cond-mat.stat-mech} , 2015 . David H. Wolpert. Extending Landauer's bound from bit erasure to arbitrary computation. arXiv:1508.05319 {cond-mat.stat-mech}, 2015."},{"key":"e_1_2_1_102_1","volume-title":"The minimal hidden computer needed to implement a visible computation. arXiv:1708.08494","author":"Wolpert David H.","year":"2017","unstructured":"David H. Wolpert , Artemy Kolchinsky , and Jeremy Owen . The minimal hidden computer needed to implement a visible computation. arXiv:1708.08494 , 2017 . David H. Wolpert, Artemy Kolchinsky, and Jeremy Owen. The minimal hidden computer needed to implement a visible computation. arXiv:1708.08494, 2017."},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232679.3232689","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3232679.3232689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:32Z","timestamp":1750282892000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232679.3232689"}},"subtitle":["New Complexity Questions Raised by Recently Discovered Thermodynamic Costs of Computation"],"short-title":[],"issued":{"date-parts":[[2018,6,13]]},"references-count":103,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,13]]}},"alternative-id":["10.1145\/3232679.3232689"],"URL":"https:\/\/doi.org\/10.1145\/3232679.3232689","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2018,6,13]]},"assertion":[{"value":"2018-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}