research-article

On the complexity of hazard-free circuits

Authors:

Christian Ikenmeyer,

Balagopal Komarath,

Christoph Lenzen,

Vladimir Lysikov,

Karteek SreenivasaiahAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 878 - 889

https://doi.org/10.1145/3188745.3188912

Published: 20 June 2018 Publication History

Abstract

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. 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.

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.

As a side result we establish the NP-completeness of several hazard detection problems.

Supplementary Material

MP4 File (6b-3.mp4)

Download
32.97 MB

References

[1]

{AB87} Noga Alon and Ravi B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1–22, 1987.

Digital Library

[2]

{AB98} Mohamad Akra and Louay Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2):195–210, 1998.

Digital Library

[3]

{AG87} Miklos Ajtai and Yuri Gurevich. Monotone versus positive. J. ACM, 34(4):1004–1015, October 1987.

Digital Library

[4]

{BEI01} J. Brzozowski, Z. Esik, and Y. Iland. Algebras for hazard detection. In Proc. 31st International Symposium on Multiple-Valued Logic, 2001.

Digital Library

[5]

{Blu85} Norbert Blum. An ω (n 4 /3 ) lower bound on the monotone network complexity of the nth degree convolution. Theoretical Computer Science, 36(Supplement C):59 – 69, 1985.

[6]

{Brz99} J. A. Brzozowski. Some applications of ternary algebras. Publicationes Mathematicae (Debrecen), 54(Supplement):583–599, 1999.

[7]

{BS95} Janusz A. Brzozowski and Carl-Johan H. Seger. Asynchronous circuits. Springer New York, 1995.

[8]

{Cal58} Samuel H. Caldwell. Switching Circuits and Logical Design. John Wiley & Sons Inc, 1958.

[9]

{CM78} Ashok K. Chandra and George Markowsky. On the number of prime implicants. Discrete Mathematics, 24(1):7 – 11, 1978.

Digital Library

[10]

{DDT78} Marc Davio, Jean-Pierre Deschamps, and André Thaysé. Discrete and switching functions. McGraw-Hill International Book Co., 1978.

[11]

{dRSdlVC12} A. Martín del Rey, G. Rodríguez Sánchez, and A. de la Villa Cuenca. On the boolean partial derivatives and their composition. Applied Mathematics Letters, 25(4):739 – 744, 2012.

[12]

{Eic65} E. B. Eichelberger. Hazard detection in combinational and sequential switching circuits. IBM J. Res. Dev., 9(2):90–99, March 1965.

Digital Library

[13]

{End01} Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, 2nd edition, 2001.

[14]

{FFL18} Stephan Friedrichs, Matthias Függer, and Christoph Lenzen. Metastability-Containing Circuits. IEEE Transactions on Computers, 2018.

[15]

To appear. Preliminary version avaiable at https://arxiv.org/abs/1606.06570. {Fri17} Stephan Friedrichs. Metastability-containing circuits, parallel distance problems, and terrain guarding. PhD thesis, Universität des Saarlandes, Postfach 151141, 66041 Saarbrücken, 2017.

[16]

{GJ79} Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

Digital Library

[17]

{Gol11} Oded Goldreich. Valiant’s polynomial-size monotone formula for Majority. online available: http://www.wisdom.weizmann.ac.il/~oded/PDF/ monomaj.pdf, 2011.

[18]

{Got48} M. Goto. Application of Three-Valued Logic to Construct the Theory of Relay Networks (in Japanese) 三値論理学の継電器回路網理論への應用. Proc. Joint Meeting IEE, IECE, and I. of Illum E. of Japan, 電気三学会東京支部連合大会講演要旨. 昭和22・23年, pages 31–32, 1948.

[19]

{Got49} M. Goto. Application of logical mathematics to the theory of relay networks (in Japanese). J. Inst. Elec. Eng. of Japan, 64(726):125–130, 1949.

[20]

{GS92} Michelangelo Grigni and Michael Sipser. Monotone complexity. In Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 57–75, New York, NY, USA, 1992. Cambridge University Press.

[21]

{HOI + 12} W. Hu, J. Oberg, A. Irturk, M. Tiwari, T. Sherwood, D. Mu, and R. Kastner. On the complexity of generating gate level information flow tracking logic. IEEE Transactions on Information Forensics and Security, 7(3):1067– 1080, June 2012.

Digital Library

[22]

{Huf57} David A. Huffman. The design and use of hazard-free switching networks. J. ACM, 4(1):47–62, January 1957.

Digital Library

[23]

{Kle38} Stephen Cole Kleene. On notation for ordinal numbers. The Journal of Symbolic Logic, 3(4):150–155, 1938.

[24]

{Kle52} Stephen Cole Kleene. Introduction to Metamathematics. North Holland, 1952.

[25]

{Kör66} Stephan Körner. Experience and theory : an essay in the philosophy of science. International library of philosophy and scientific method. Routledge & Kegan Paul, London, 1966.

[26]

{LG14} François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, pages 296–303, New York, NY, USA, 2014. ACM.

Digital Library

[27]

{LMS11} Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, (105):41–71, 2011.

[28]

{Mal14} Grzegorz Malinowski. Kleene logic and inference. Bulletin of the Section of Logic, 43(1/2):42–52, 2014.

[29]

{Mar81} Leonard R. Marino. General theory of metastable operation. IEEE Trans. Computers, 30(2):107–115, 1981.

Digital Library

[30]

{MG76} K. Mehlhorn and Z. Galil. Monotone switching circuits and boolean matrix product. Computing, 16(1):99–111, Mar 1976.

[31]

{Muk72} M. Mukaidono. On the b-ternary logical function - a ternary logic considering ambiguity. Systems, Computers, Controls, 3(3):27–36, 1972.

[32]

{Muk83a} M. Mukaidono. Advanced results on application of fuzzy switching functions to hazard detection. In P.P. Wong, editor, Advances in Fuzzy Sets, Possibility Theory and Applications, pages 335–349. Plenum Publishing Corporation, 1983.

[33]

{Muk83b} M. Mukaidono. Regular ternary logic functions – ternary logic functions suitable for treating ambiguity. In Proc. 13th International Symposium on Multiple-Valued Logic, pages 286–291. IEEE Computer Society Press, 1983.

[34]

{ND92} S. M. Nowick and D. L. Dill. Exact two-level minimization of hazardfree logic with multiple-input changes. In 1992 IEEE/ACM International Conference on Computer-Aided Design, pages 626–630, Nov 1992.

Digital Library

[35]

{NW96} Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. computational complexity, 6(3):217–234, Sep 1996.

Digital Library

[36]

{Pat75} Michael S. Paterson. Complexity of monotone networks for boolean matrix product. Theoretical Computer Science, 1(1):13 – 20, 1975.

[37]

{PCRF79} Pedro Ponce-Cruz and Fernando D. Ramírez-Figueroa. Intelligent Control Systems with LabVIEW. Springer-Verlag London, 1979.

[38]

STOC’18, June 25–29, 2018, Los Angeles, CA, USA Ikenmeyer, Komarath, Lenzen, Lysikov, Mokhov, Sreenivasaiah {Pra74} Vaughan R. Pratt. The power of negative thinking in multiplying boolean matrices. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, pages 80–83, New York, NY, USA, 1974. ACM.

Digital Library

[39]

{Raz85} Alexander A. Razborov. Lower bounds on monotone complexity of the logical permanent. Math. Notes, 37(6):485–493, 1985.

[40]

{Roj96} Raul Rojas. Neural Networks - A Systematic Introduction. Springer-Verlag, Berlin, New-York, 1996.

Digital Library

[41]

{RW92} Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth. J. ACM, 39(3):736–744, 1992.

Digital Library

[42]

{Str69} Volker Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354–356, 1969.

Digital Library

[43]

{Tar88} É. Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, Mar 1988.

[44]

{TWM + 09} Mohit Tiwari, Hassan M.G. Wassel, Bita Mazloom, Shashidhar Mysore, Frederic T. Chong, and Timothy Sherwood. Complete information flow tracking from the gates up. SIGARCH Comput. Archit. News, 37(1):109– 120, March 2009.

Digital Library

[45]

{TY12} G. Tarawneh and A. Yakovlev. An rtl method for hiding clock domain crossing latency. In 2012 19th IEEE International Conference on Electronics, Circuits, and Systems (ICECS 2012), pages 540–543, Dec 2012.

[46]

{TYM14} G. Tarawneh, A. Yakovlev, and T. Mak. Eliminating synchronization latency using sequenced latching. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 22(2):408–419, Feb 2014.

Digital Library

[47]

{Ung95} S. H. Unger. Hazards, critical races, and metastability. IEEE Transactions on Computers, 44(6):754–768, Jun 1995.

Digital Library

[48]

{Weg82} Ingo Wegener. Boolean functions whose monotone complexity is of size n 2 / log n. 21:213–224, 11 1982.

[49]

{Yao89} A. C. Yao. Circuits and local computation. In Proceedings of the Twentyfirst Annual ACM Symposium on Theory of Computing, STOC ’89, pages 186–196, New York, NY, USA, 1989. ACM.

Digital Library

[50]

{YR64} Michael Yoeli and Shlomo Rinon. Application of ternary algebra to the study of static hazards. J. ACM, 11(1):84–97, jan 1964.

Digital Library

[51]

{ZKK79} Y. Zisapel, M. Krieger, and J. Kella. Detection of hazards in combinational switching circuits. IEEE Transactions on Computers, C-28(1):52–56, Jan 1979.

Digital Library

Cited By

Abu-AlShaeer MAbdulkareem SMustafa FYakymenko N(2024)A Path to Safer Digital Systems Using Proactive Hazard Analysis in Logic Circuit Design2024 35th Conference of Open Innovations Association (FRUCT)10.23919/FRUCT61870.2024.10516411(11-21)Online publication date: 24-Apr-2024
https://doi.org/10.23919/FRUCT61870.2024.10516411
Ikenmeyer CKomarath BLenzen CLysikov VMokhov ASreenivasaiah K(2019)On the Complexity of Hazard-free CircuitsJournal of the ACM10.1145/332012366:4(1-20)Online publication date: 23-Aug-2019
https://dl.acm.org/doi/10.1145/3320123
Bund JLenzen CMedina M(2019)Optimal Metastability-Containing Sorting via Parallel Prefix ComputationIEEE Transactions on Computers10.1109/TC.2019.2939818(1-1)Online publication date: 2019
https://doi.org/10.1109/TC.2019.2939818
Show More Cited By

Index Terms

On the complexity of hazard-free circuits
1. Theory of computation
  1. Computational complexity and cryptography
    1. Circuit complexity

Recommendations

On the Complexity of Hazard-free Circuits
Networking, Computational Complexity, Design and Analysis of Algorithms, Real Computation, Algorithms, Online Algorithms and Computer-aided Verification

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 ...
Computational Complexity of Controllability/Observability Problems for Combinational Circuits

The computational complexity of fault detection problems and various controllability and observability problems for combinational logic circuits are analyzed. It is shown that the fault detection problem is still NP-complete for monotone circuits ...
Semi-unbounded fan-in circuits: Boolean vs. arithmetic
SCT '95: Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95)

We prove that polynomial size semi-unbounded fan-in Boolean circuits of depth d can be simulated by polynomial size semi-unbounded fan-in arithmetic circuits of depth O(d+log n), where the arithmetic operations +, -, /spl times/ are performed in an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

EPSRC
ERC

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
213
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abu-AlShaeer MAbdulkareem SMustafa FYakymenko N(2024)A Path to Safer Digital Systems Using Proactive Hazard Analysis in Logic Circuit Design2024 35th Conference of Open Innovations Association (FRUCT)10.23919/FRUCT61870.2024.10516411(11-21)Online publication date: 24-Apr-2024
https://doi.org/10.23919/FRUCT61870.2024.10516411
Ikenmeyer CKomarath BLenzen CLysikov VMokhov ASreenivasaiah K(2019)On the Complexity of Hazard-free CircuitsJournal of the ACM10.1145/332012366:4(1-20)Online publication date: 23-Aug-2019
https://dl.acm.org/doi/10.1145/3320123
Bund JLenzen CMedina M(2019)Optimal Metastability-Containing Sorting via Parallel Prefix ComputationIEEE Transactions on Computers10.1109/TC.2019.2939818(1-1)Online publication date: 2019
https://doi.org/10.1109/TC.2019.2939818
Friedrichs SFugger MLenzen C(2018)Metastability-Containing CircuitsIEEE Transactions on Computers10.1109/TC.2018.2808185(1-1)Online publication date: 2018
https://doi.org/10.1109/TC.2018.2808185

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents