ECCC-Report TR20-102https://eccc.weizmann.ac.il/report/2020/102Comments and Revisions published for TR20-102en-usMon, 20 Jul 2020 21:18:46 +0300
Revision 1
| Notes on Hazard-Free Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2020/102#revision1The 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.Mon, 20 Jul 2020 21:18:46 +0300https://eccc.weizmann.ac.il/report/2020/102#revision1
Paper TR20-102
| Notes on Hazard-Free Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2020/102The 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.Thu, 09 Jul 2020 22:01:07 +0300https://eccc.weizmann.ac.il/report/2020/102