Everyone is welcome to attend the online QuSoft seminar with Rahul Ilango (MIT). Title of his lecture: Towards Hardness for the Minimum Circuit Size Problem.
Abstract:
Understanding the computational complexity of the Minimum Circuit Size Problem (MCSP) has been a longstanding goal in theoretical computer science, dating back to at least the 1950s. Despite this long history of study, relatively little is known unconditionally about the complexity of MCSP. In particular, it is a major open problem to show MCSP is intractable
under standard (worst-case) complexity assumptions. In recent years, this question has gained renewed importance as researchers have discovered connections between MCSP and a growing number of fields, including to cryptography, learning theory, and average-case complexity. In this talk, I will discuss some of the context related to research on MCSP and overview three recent joint works that prove hardness results for several natural variants of MCSP. This includes NP-hardness for an oracle-version, a multi-output version, and a constant-depth formula version. I will discuss the last result in the most detail and highlight an application that establishes the existence of functions with a 2^{\Omega_d(n)} additive gap between their depth-d and depth-(d+1) formula complexity.
Please contact Jop Briet or Subhasree Patro if you like to join.
