On the complexity of hazard-Free circuits
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Titel | STOC 2018 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |
Antal sider | 14 |
Udgivelsessted | New York |
Forlag | Association for Computing Machinery |
Publikationsdato | 20 jun. 2018 |
Sider | 253-266 |
ISBN (Elektronisk) | 978-1-4503-5559-9 |
DOI | |
Status | Udgivet - 20 jun. 2018 |
Eksternt udgivet | Ja |
Begivenhed | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, USA Varighed: 25 jun. 2018 → 29 jun. 2018 |
Konference
Konference | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|
Land | USA |
By | Los Angeles |
Periode | 25/06/2018 → 29/06/2018 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |
Navn | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|
ISSN | 0737-8017 |
ID: 232711583