ePrints

On the complexity of hazard-free circuits

Lookup NU author(s): Dr Andrey Mokhov

Downloads

• Published version [.pdf]

Licence

This work is licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0).

Abstract

© 2019 Copyright held by the owner/author(s).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.

Publication metadata

Author(s): Ikenmeyer C, Komarath B, Lenzen C, Lysikov V, Mokhov A, Sreenivasaiah K

Publication type: Article

Publication status: Published

Journal: Journal of the ACM

Year: 2019

Volume: 66

Issue: 4

Print publication date: 01/08/2019

Online publication date: 01/08/2019

Acceptance date: 31/03/2019

Date deposited: 14/10/2019

ISSN (print): 0004-5411

ISSN (electronic): 1557-735X

Publisher: Association for Computing Machinery

URL: https://doi.org/10.1145/3320123

DOI: 10.1145/3320123

Altmetrics

Funding

Share