ECCC-Report TR20-102https://eccc.weizmann.ac.il/report/2020/102Comments and Revisions published for TR20-102en-usTue, 22 Dec 2020 16:01:24 +0200
Revision 2
| Notes on Hazard-Free Circuits |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2020/102#revision2The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybersecurity. 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. Via an amazingly simple
proof, we also strengthen a recent result Ikenmeyer et al. [J. ACM, 66:4 (2019)]: not only the complexities of hazard-free and monotone circuits for monotone Boolean functions do coincide, but every optimal hazard-free circuit for a monotone Boolean function must be monotone. Then we show that hazard-free circuit complexity of a very simple (non-monotone) Boolean function is super-polynomially larger than its unrestricted circuit complexity. This function accepts a Boolean $n\times n$ matrix iff every row and every column has exactly one 1-entry. Finally, we show that every Boolean function of $n$ variables can be computed by a hazard-free circuit of size~$O(2^n/n)$.Tue, 22 Dec 2020 16:01:24 +0200https://eccc.weizmann.ac.il/report/2020/102#revision2
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