#### Alladi Ramakrishnan Hall

#### On the complexity of hazard-free circuits

#### K Balagopal

##### Saarland University

*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.

Done