Date & Time: Thursday, January 29, 2015, 14:30-16:00.
Venue: Room 216

Title: Monotone circuit lower bounds

Speaker: Srikanth Srinivasan, IIT Bombay

Abstract: I will talk about some classical monotone Boolean circuit lower bounds. Boolean circuits are very general models of computation. Though it is known that `most' computational problems do not have `efficient' Boolean circuits, we do not yet know explicit examples of such hard problems. Classical results from the 1980s have been able to establish such statements for certain special classes of Boolean circuits. In this talk, we will see such a result for Monotone Boolean circuits.