Speaker: Meena Mahajan, Institute of Mathematical Sciences, Chennai
Abstract: The building blocks of the digital age computers are gates implementing Boolean functions. Every Boolean function can be implemented using just binary AND, binary OR, and unary NOT gates. Furthermore, certain Boolean functions, the monotone functions, do not even need the NOT gates. Nonetheless, even for monotone functions, using NOT gates can significantly reduce the size of the required circuitry. In this talk, we explore this mystery and survey known facts.