On the complexity of hazard-Free circuits

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

  • Christian Ikenmeyer
  • Lysikov, Vladimir
  • Balagopal Komarath
  • Andrey Mokhov
  • Christoph Lenzen
  • Karteek Sreenivasaiah

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.

Original languageEnglish
Title of host publicationSTOC 2018 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Number of pages14
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Publication date20 Jun 2018
ISBN (Electronic)978-1-4503-5559-9
Publication statusPublished - 20 Jun 2018
Externally publishedYes
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: 25 Jun 201829 Jun 2018


Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
LandUnited States
ByLos Angeles
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)
SeriesProceedings of the Annual ACM Symposium on Theory of Computing

    Research areas

  • Boolean circuits, Computational complexity, Hazards, Monotone circuits

ID: 232711583