Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-102 | 20th July 2020 21:18

Notes on Hazard-Free Circuits

RSS-Feed




Revision #1
Authors: Stasys Jukna
Accepted on: 20th July 2020 21:18
Downloads: 27
Keywords: 


Abstract:

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. We show that a DeMorgan circuit is hazard-free if and only if the circuit produces (purely syntactically) all prime implicants as well as all prime implicates of the Boolean function it computes.
This extends to arbitrary DeMorgan circuits a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for special depth-two circuits.
Also, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have recently shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the monotone circuit complexity of the monotone Boolean function which accepts an input $x$ iff $f(z)=1$ for some vector $z\leq x$. We give a short and amazingly simple proof of this interesting result. Finally, we give a very simple (non-monotone) Boolean function whose hazard-free circuit complexity is super-polynomially larger than its unrestricted circuit complexity.



Changes to previous version:

The extension of the (classical) result of Eichelberger (Theorem 1) is now "granulated": a more exact characterization of hazards is given (Theorems 4 and 5). The progress towards estimating the Shannon function of hazard-free circuits, recently made by Nitin Saurabh, is now also sketched.


Paper:

TR20-102 | 9th July 2020 22:00

Notes on Hazard-Free Circuits





TR20-102
Authors: Stasys Jukna
Publication: 9th July 2020 22:01
Downloads: 169
Keywords: 


Abstract:

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the monotone circuit complexity of the monotone Boolean function which accepts an input $x$ iff $f(z)=1$ for some vector $z\leq x$. We give a short and amazingly simple proof of this interesting result. We also show that a circuit is hazard-free if and only if the circuit and its dual produce (purely syntactically) all prime implicants of the functions they compute. This extends a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for depth-two circuits producing no terms containing a variable together with its negation. Finally, we give a very simple non-monotone Boolean function whose hazard-free circuit complexity is super-polynomially larger than its unrestricted circuit complexity.



ISSN 1433-8092 | Imprint