Hazard-free Circuit Complexity (Track A)

Speaker: Prof. Christian Ikenmeyer (University of Warwick) Abstract: We discuss the concept of Boolean circuits and their hazards. Hazards can always be removed, but this requires a large increase in the circuit size. When the hazards are sufficiently tame, then removing them is possible with only a polynomially bounded size blow-up. This is joint work with Komarath-Lenzen-Lysikov-Mokhov-Sreenivasaiah. The topic has some connections to the recent work of Deligkas-Fearnley-Hollender-Melissourgos.