Abstract | ||
---|---|---|
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.
|
Year | DOI | Venue |
---|---|---|
2019 | 10.1145/3320123 | STOC '18: Symposium on Theory of Computing
Los Angeles
CA
USA
June, 2018 |
Keywords | DocType | Volume |
Boolean circuits,Hazards,computational complexity,monotone circuits | Journal | 66 |
Issue | ISSN | ISBN |
4 | 0004-5411 | 978-1-4503-5559-9 |
Citations | PageRank | References |
0 | 0.34 | 19 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christian Ikenmeyer | 1 | 0 | 0.68 |
Balagopal Komarath | 2 | 4 | 3.16 |
Christoph Lenzen | 3 | 584 | 40.61 |
Vladimir Lysikov | 4 | 1 | 2.40 |
Andrey Mokhov | 5 | 136 | 26.57 |
Karteek Sreenivasaiah | 6 | 13 | 5.30 |