We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}
\item If there exists a perfect (imperfect) $IO$ that is computationally secure ... more >>>

For every fixed $k\ge3$, we construct an explicit total Boolean function in the $k$-player number-on-forehead model with public-coin randomized communication complexity $O_k(1)$ and nondeterministic communication complexity $\Omega_k(n)$, where $n$ is the number of bits on each forehead. This extends the explicit three-player separations of Kelley, Lovett, and Meka (STOC 2024) ... more >>>