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.