Invited Talk by Dr. Balagopal Komarath on On the complexity of hazard-free circuits
Title: On the complexity of hazard-free circuits
Speaker: Dr. Balagopal Komarath, Saarland University
Host Faculty: Dr. Karteek sreenivasaiah
Room No: A-220, academic block A.
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.
Dr. Balagopal Komarath is a postdoc researcher in the complexity group at Saarland University, Germany. He obtained his PhD from IITM in 2015. He research interests are in circuit complexity and algorithms.
Tuesday, December 12, 2017 - 14:30