Towards Hardness for the Minimum Circuit Size Problem

Towards Hardness for the Minimum Circuit Size Problem (via Zoom)

Abstract: Understanding the computational complexity of the Minimum Circuit Size Problem (MCSP) is a longstanding goal in theoretical computer science, dating back to at least the 1950s. In particular, it is a major open problem to show MCSP is intractable under standard (worst-case) complexity assumptions. Moreover, this question has gained renewed importance as researchers have discovered connections between MCSP and a growing number of fields, including cryptography, learning theory, and average-case complexity. 

In this talk, I will briefly recap some of this context for research on MCSP and then overview recent joint works that prove hardness results for several natural variants of MCSP, including versions for constant depth formulas and partial functions. Finally, I will end by highlighting an application of our techniques which establishes the existence of functions with a 2^{\Omega_d(n)} additive gap between their depth-d and depth-(d+1) formula complexity.

Bio: I am a second-year PhD student studying Theoretical Computer Science at MIT advised by Ryan Williams. Before this, I was an undergraduate at Rutgers University, where I was lucky enough to discuss research and learn from Eric Allender and Michael Saks. I also participated twice in the DIMACS REU program.

Most of my research is in the field of Computational Complexity Theory, which quantifies the amount of resources — like time and hardware — needed to solve computational tasks, like finding the fastest route from point A to point B on a map.