@online{Ikenmeyer_Komarath2017,
TITLE = {On the Complexity of Hazard-free Circuits},
AUTHOR = {Ikenmeyer, Christian and Komarath, Balagopal and Lenzen, Christoph and Lysikov, Vladimir and Mokhov, Andrey and Sreenivasaiah, Karteek},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1711.01904},
EPRINT = {1711.01904},
EPRINTTYPE = {arXiv},
YEAR = {2017},
ABSTRACT = {The problem of constructing hazard-free Boolean circuits dates back to the<br>1940s and is an important problem in circuit design. Our main lower-bound<br>result unconditionally shows the existence of functions whose circuit<br>complexity is polynomially bounded while every hazard-free implementation is<br>provably of exponential size. Previous lower bounds on the hazard-free<br>complexity were only valid for depth 2 circuits. The same proof method yields<br>that every subcubic implementation of Boolean matrix multiplication must have<br>hazards.<br> These results follow from a crucial structural insight: Hazard-free<br>complexity is a natural generalization of monotone complexity to all (not<br>necessarily monotone) Boolean functions. Thus, we can apply known monotone<br>complexity lower bounds to find lower bounds on the hazard-free complexity. We<br>also lift these methods from the monotone setting to prove exponential<br>hazard-free complexity lower bounds for non-monotone functions.<br> As our main upper-bound result we show how to efficiently convert a Boolean<br>circuit into a bounded-bit hazard-free circuit with only a polynomially large<br>blow-up in the number of gates. Previously, the best known method yielded<br>exponentially large circuits in the worst case, so our algorithm gives an<br>exponential improvement.<br> As a side result we establish the NP-completeness of several hazard detection<br>problems.<br>},
}