Fall 2018

Natural Properties, MCSP, and Proving Circuit Lower Bounds

Thursday, September 13th, 2018 12:00 pm12:30 pm

Add to Calendar


Valentine Kabanets (Simon Fraser University)

The concept of  "natural properties" of Razborov and Rudich arose in the context of proving circuit lower bounds for explicit boolean functions, and is used to argue about the limitations of current proof techniques. MCSP (Min Circuit Size Problem), is a close relative ("worst-case version") of the "natural property" whose complexity is still wide open. Understanding the complexity of MCSP also appears to be intimately linked with the problem of proving circuit lower bounds. I'll discuss some known connections among "natural properties," (variants of) MCSP, and circuit lower bounds.