{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T22:56:12Z","timestamp":1776984972028,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T00:00:00Z","timestamp":1566518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["716562"],"award-info":[{"award-number":["716562"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N031768\/1"],"award-info":[{"award-number":["EP\/N031768\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards.<\/jats:p>\n          <jats:p>These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions.<\/jats:p>\n          <jats:p>As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement.<\/jats:p>\n          <jats:p>As a side result, we establish the NP-completeness of several hazard detection problems.<\/jats:p>","DOI":"10.1145\/3320123","type":"journal-article","created":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T12:00:08Z","timestamp":1566561608000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Hazard-free Circuits"],"prefix":"10.1145","volume":"66","author":[{"given":"Christian","family":"Ikenmeyer","sequence":"first","affiliation":[{"name":"Max Planck Institute for Software Systems, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balagopal","family":"Komarath","sequence":"additional","affiliation":[{"name":"Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Lenzen","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Lysikov","sequence":"additional","affiliation":[{"name":"Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrey","family":"Mokhov","sequence":"additional","affiliation":[{"name":"Newcastle University, Newcastle upon Tyne, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karteek","family":"Sreenivasaiah","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Hyderabad, , Hyderabad, Telangana State, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90030-1"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 31st International Symposium on Multiple-Valued Logic.","author":"Brzozowski J.","unstructured":"J. Brzozowski , Z. Esik , and Y. Iland . 2001. Algebras for hazard detection . In Proceedings of the 31st International Symposium on Multiple-Valued Logic. J. Brzozowski, Z. Esik, and Y. Iland. 2001. Algebras for hazard detection. In Proceedings of the 31st International Symposium on Multiple-Valued Logic."},{"key":"e_1_2_1_6_1","first-page":"583","article-title":"Some applications of ternary algebras","volume":"54","author":"Brzozowski J. A.","year":"1999","unstructured":"J. A. Brzozowski . 1999 . Some applications of ternary algebras . Publicationes Mathematicae (Debrecen) 54, Supplement (1999), 583 -- 599 . J. A. Brzozowski. 1999. Some applications of ternary algebras. Publicationes Mathematicae (Debrecen) 54, Supplement (1999), 583--599.","journal-title":"Publicationes Mathematicae (Debrecen)"},{"key":"e_1_2_1_7_1","volume-title":"Asynchronous Circuits","author":"Brzozowski Janusz A.","unstructured":"Janusz A. Brzozowski and Carl-Johan H. Seger . 1995. Asynchronous Circuits . Springer , New York . Janusz A. Brzozowski and Carl-Johan H. Seger. 1995. Asynchronous Circuits. Springer, New York."},{"key":"e_1_2_1_8_1","volume-title":"Corliss","author":"Martin B\u00fccker H.","year":"2006","unstructured":"H. Martin B\u00fccker and George F . Corliss . 2006 . A bibliography of automatic differentiation. In Automatic Differentiation: Applications, Theory, and Implementations, Martin B\u00fccker, George Corliss, Uwe Naumann, Paul Hovland, and Boyana Norris (Eds.). Springer-Verlag , Berlin, 321--322. H. Martin B\u00fccker and George F. Corliss. 2006. A bibliography of automatic differentiation. In Automatic Differentiation: Applications, Theory, and Implementations, Martin B\u00fccker, George Corliss, Uwe Naumann, Paul Hovland, and Boyana Norris (Eds.). Springer-Verlag, Berlin, 321--322."},{"key":"e_1_2_1_9_1","volume-title":"Switching Circuits and Logical Design","author":"Caldwell Samuel H.","unstructured":"Samuel H. Caldwell . 1958. Switching Circuits and Logical Design . John Wiley 8 Sons. Samuel H. Caldwell. 1958. Switching Circuits and Logical Design. John Wiley 8 Sons."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90168-1"},{"key":"e_1_2_1_11_1","volume-title":"Discrete and Switching Functions","author":"Davio Marc","unstructured":"Marc Davio , Jean-Pierre Deschamps , and Andr\u00e9 Thays\u00e9 . 1978. Discrete and Switching Functions . McGraw-Hill . Marc Davio, Jean-Pierre Deschamps, and Andr\u00e9 Thays\u00e9. 1978. Discrete and Switching Functions. McGraw-Hill."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2011.10.013"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.92.0090"},{"key":"e_1_2_1_14_1","volume-title":"A Mathematical Introduction to Logic","author":"Enderton Herbert B.","unstructured":"Herbert B. Enderton . 2001. A Mathematical Introduction to Logic ( 2 nd ed.). Academic Press . Herbert B. Enderton. 2001. A Mathematical Introduction to Logic (2nd ed.). Academic Press.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2018.2808185"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Joint Meeting IEE, IECE, and I. of Illum. E. of Japan, \u96fb\u6c17\u4e09\u5b66\u4f1a\u6771\u4eac\u652f\u90e8\u9023\u5408\u5927\u4f1a\u8b1b\u6f14\u8981\u65e8. \u662d\u548c 22 \u00b7 23\u5e74","author":"Goto M.","year":"1948","unstructured":"M. Goto . 1948 . Application of three-valued logic to construct the theory of relay networks (in Japanese) \u4e09\u5024\u8ad6\u7406\u5b66\u306e\u7d99\u96fb\u5668\u56de\u8def\u7db2\u7406\u8ad6\u3078\u306e\u61c9\u7528 . Proceedings of the Joint Meeting IEE, IECE, and I. of Illum. E. of Japan, \u96fb\u6c17\u4e09\u5b66\u4f1a\u6771\u4eac\u652f\u90e8\u9023\u5408\u5927\u4f1a\u8b1b\u6f14\u8981\u65e8. \u662d\u548c 22 \u00b7 23\u5e74 (1948), 31--32. M. Goto. 1948. Application of three-valued logic to construct the theory of relay networks (in Japanese) \u4e09\u5024\u8ad6\u7406\u5b66\u306e\u7d99\u96fb\u5668\u56de\u8def\u7db2\u7406\u8ad6\u3078\u306e\u61c9\u7528 . Proceedings of the Joint Meeting IEE, IECE, and I. of Illum. E. of Japan, \u96fb\u6c17\u4e09\u5b66\u4f1a\u6771\u4eac\u652f\u90e8\u9023\u5408\u5927\u4f1a\u8b1b\u6f14\u8981\u65e8. \u662d\u548c 22 \u00b7 23\u5e74 (1948), 31--32."},{"key":"e_1_2_1_18_1","first-page":"125","article-title":"Application of logical mathematics to the theory of relay networks (in Japanese)","volume":"64","author":"Goto M.","year":"1949","unstructured":"M. Goto . 1949 . Application of logical mathematics to the theory of relay networks (in Japanese) . J. Inst. Elec. Eng. Japan 64 , 726 (1949), 125 -- 130 . M. Goto. 1949. Application of logical mathematics to the theory of relay networks (in Japanese). J. Inst. Elec. Eng. Japan 64, 726 (1949), 125--130.","journal-title":"J. Inst. Elec. Eng. Japan"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/167687.167706"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2012.2189105"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/320856.320866"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188912"},{"key":"e_1_2_1_23_1","volume-title":"Boolean Function Complexity\u2014Advances and Frontiers. Algorithms and combinatorics","author":"Jukna Stasys","unstructured":"Stasys Jukna . 2012. Boolean Function Complexity\u2014Advances and Frontiers. Algorithms and combinatorics , Vol. 27 . Springer . Stasys Jukna. 2012. Boolean Function Complexity\u2014Advances and Frontiers. Algorithms and combinatorics, Vol. 27. Springer."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/2267778"},{"key":"e_1_2_1_25_1","unstructured":"Stephen Cole Kleene. 1952. Introduction to Metamathematics. North Holland.  Stephen Cole Kleene. 1952. Introduction to Metamathematics. North Holland."},{"key":"e_1_2_1_26_1","volume-title":"Experience and Theory : An Essay in the Philosophy of Science","author":"K\u00f6rner Stephan","unstructured":"Stephan K\u00f6rner . 1966. Experience and Theory : An Essay in the Philosophy of Science . Routledge 8 Kegan Paul, London. Stephan K\u00f6rner. 1966. Experience and Theory : An Essay in the Philosophy of Science. Routledge 8 Kegan Paul, London."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_28_1","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . 2011 . Lower bounds based on the exponential time hypothesis . Bull. EATCS 105 (2011), 41 -- 71 . Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41--71.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_29_1","first-page":"42","article-title":"Kleene logic and inference","volume":"43","author":"Malinowski Grzegorz","year":"2014","unstructured":"Grzegorz Malinowski . 2014 . Kleene logic and inference . Bull. Section Logic 43 , 1\/2 (2014), 42 -- 52 . Grzegorz Malinowski. 2014. Kleene logic and inference. Bull. Section Logic 43, 1\/2 (2014), 42--52.","journal-title":"Bull. Section Logic"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1963635.1963638"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and Z. Galil. 1976. Monotone switching circuits and boolean matrix product. Computing 16 1 (01 Mar. 1976) 99--111.  K. Mehlhorn and Z. Galil. 1976. Monotone switching circuits and boolean matrix product. Computing 16 1 (01 Mar. 1976) 99--111.","DOI":"10.1007\/BF02241983"},{"key":"e_1_2_1_32_1","first-page":"27","article-title":"On the B-ternary logical function\u2014A ternary logic considering ambiguity","volume":"3","author":"Mukaidono M.","year":"1972","unstructured":"M. Mukaidono . 1972 . On the B-ternary logical function\u2014A ternary logic considering ambiguity . Syst. Comput. Controls 3 , 3 (1972), 27 -- 36 . M. Mukaidono. 1972. On the B-ternary logical function\u2014A ternary logic considering ambiguity. Syst. Comput. Controls 3, 3 (1972), 27--36.","journal-title":"Syst. Comput. Controls"},{"key":"e_1_2_1_33_1","volume-title":"Advances in Fuzzy Sets, Possibility Theory and Applications","author":"Mukaidono M.","unstructured":"M. Mukaidono . 1983. Advanced results on application of fuzzy switching functions to hazard detection . In Advances in Fuzzy Sets, Possibility Theory and Applications , P. P. Wong (Ed.). Plenum Publishing , 335--349. M. Mukaidono. 1983. Advanced results on application of fuzzy switching functions to hazard detection. In Advances in Fuzzy Sets, Possibility Theory and Applications, P. P. Wong (Ed.). Plenum Publishing, 335--349."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 13th International Symposium on Multiple-Valued Logic. IEEE Computer Society Press, 286--291","author":"Mukaidono M.","year":"1983","unstructured":"M. Mukaidono . 1983 . Regular ternary logic functions\u2014Ternary logic functions suitable for treating ambiguity . In Proceedings of the 13th International Symposium on Multiple-Valued Logic. IEEE Computer Society Press, 286--291 . M. Mukaidono. 1983. Regular ternary logic functions\u2014Ternary logic functions suitable for treating ambiguity. In Proceedings of the 13th International Symposium on Multiple-Valued Logic. IEEE Computer Society Press, 286--291."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. 626--630","author":"Nowick S. M.","unstructured":"S. M. Nowick and D. L. Dill . 1992. Exact two-level minimization of hazard-free logic with multiple-input changes . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. 626--630 . S. M. Nowick and D. L. Dill. 1992. Exact two-level minimization of hazard-free logic with multiple-input changes. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. 626--630."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/901299"},{"key":"e_1_2_1_37_1","volume-title":"Ram\u00edrez-Figueroa","author":"Ponce-Cruz Pedro","year":"1979","unstructured":"Pedro Ponce-Cruz and Fernando D . Ram\u00edrez-Figueroa . 1979 . Intelligent Control Systems with LabVIEW. Springer-Verlag , London. Pedro Ponce-Cruz and Fernando D. Ram\u00edrez-Figueroa. 1979. Intelligent Control Systems with LabVIEW. Springer-Verlag, London."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803887"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01157687"},{"key":"e_1_2_1_41_1","volume-title":"Neural Networks\u2014A Systematic Introduction","author":"Rojas Raul","unstructured":"Raul Rojas . 1996. Neural Networks\u2014A Systematic Introduction . Springer-Verlag , Berlin . Raul Rojas. 1996. Neural Networks\u2014A Systematic Introduction. Springer-Verlag, Berlin."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 19th IEEE International Conference on Electronics, Circuits, and Systems (ICECS\u201912)","author":"Tarawneh G.","unstructured":"G. Tarawneh and A. Yakovlev . 2012. An RTL method for hiding clock domain crossing latency . In Proceedings of the 19th IEEE International Conference on Electronics, Circuits, and Systems (ICECS\u201912) . 540--543. G. Tarawneh and A. Yakovlev. 2012. An RTL method for hiding clock domain crossing latency. In Proceedings of the 19th IEEE International Conference on Electronics, Circuits, and Systems (ICECS\u201912). 540--543."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2013.2243177"},{"key":"e_1_2_1_45_1","first-page":"1","article-title":"The gap between monotone and non-monotone circuit complexity is exponential","volume":"8","year":"1988","unstructured":"\u00c9. Tardos. 1988 . The gap between monotone and non-monotone circuit complexity is exponential . Combinatorica 8 , 1 (Mar. 1988), 141--142. \u00c9. Tardos. 1988. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica 8, 1 (Mar. 1988), 141--142.","journal-title":"Combinatorica"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508284.1508258"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.391185"},{"key":"e_1_2_1_48_1","volume-title":"Boolean functions whose monotone complexity is of size n<sup>2<\/sup>\/log n. Lect. Notes Comput. Sci. 21 (Nov","author":"Wegener Ingo","year":"1982","unstructured":"Ingo Wegener . 1982. Boolean functions whose monotone complexity is of size n<sup>2<\/sup>\/log n. Lect. Notes Comput. Sci. 21 (Nov . 1982 ), 213--224. Ingo Wegener. 1982. Boolean functions whose monotone complexity is of size n<sup>2<\/sup>\/log n. Lect. Notes Comput. Sci. 21 (Nov. 1982), 213--224."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73025"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/321203.321214"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675222"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3320123","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3320123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:52Z","timestamp":1750273492000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3320123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,23]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3320123"],"URL":"https:\/\/doi.org\/10.1145\/3320123","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,23]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}