July 15, 2019, 9:30 AM - 11:00 AM
Hill Center, Room 116
Eric Allender, Rutgers University
The Minimum Circuit Size Problem (MCSP) takes as input the truth-table of a Boolean function f, and asks about the size of the smallest circuit computing f. MCSP has been the subject of a large amount of research lately. This talk will survey some of this work and will try to explain why MCSP is attracting so much attention.
Video This is a video of a talk given on a blackboard.