CS Forum: "Hazard-free Circuits" Christoph Lenzen, Max-Planck-Institut für Informatik
CS department's public guest lecture, open to everyone free-of-charge.
Map © OpenStreetMap. Some rights reserved.
Christoph Lenzen
Max-Planck-Institut für Informatik
Host: Professor Jukka Suomela
Time: 14:15 (coffee at 14:00)
Venue: T3, CS building
Hazard-free Circuits
Abstract:
Computers and other hardware operate using the Boolean abstraction: signals are interpreted as logical 0 or 1, respectively, depending on whether their voltage is low or high. However, in some important cases, this abstraction is insufficient to accurately describe what happens in a circuit, as signals may take on intermediate values that are neither "clearly 0" nor "clearly 1." In such situations, a suitable abstraction is the ternary Kleene logic, which extends the operations of gates in a natural way by describing all "unclean" signals by a third symbol U. The goal is to control how U inputs affect the output of circuits, ideally ensuring (correct) Boolean outputs whenever possible. When a Boolean output could be achieved but a circuit does not guarantee this, this is referred to as a hazard of the circuit.
In this talk, I will give an overview of recent results (appearing at STOC'18) on avoiding hazards in circuits. In particular, I will discuss how monotone circuit lower bounds imply strong (unconditional!) lower bounds on the size of hazard-free circuits, for computational problems that permit small circuits (with hazards). On the positive side, I show general transformations that derive hazard-free circuits from arbitrary circuits. The talk will be accessible to a general CS audience; in particular, prior knowledge on circuit complexity is neither assumed nor needed (which is fortunate, as the speaker does not possess it either).
Short bio:
Christoph Lenzen received a diploma in mathematics from the University of Bonn and a Ph.D. from ETH Zurich. After postdoc positions at the Hebrew University of Jerusalem, the Weizmann Institute of Science, and MIT, he took on his current position as group leader at MPI for Informatics, Saarbrücken, Germany. His research interests span from the theory of distributed systems to designing fault-tolerant hardware. An ERC starting grant supports his work in the latter area, which lead to the results presented in this talk.