« search calendars« CoSP Workshop and School on Algorithms and Complexity
« The Minimum Circuit Size Problem: What is it? And Why Do We Care?
The Minimum Circuit Size Problem: What is it? And Why Do We Care?
July 15, 2019, 9:30 AM - 11:00 AM
Location:
Hill Center, Room 116
Rutgers University
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.