The Minimum Circuit Size problem is a fundamental problem in theoretical computer science, connecting cryptography, learning theory, structural complexity, etc., One of the longstanding open problems is whether determining the size of a smallest circuit for a boolean function is equivalent to finding a minimum-sized circuit for the function. If one can find a minimum-sized circuit, one can certainly determine the minimum size required to compute a given function. The converse -- a search-to-decision reduction -- is not known. We haven't yet ruled out the possibility that the decision problem takes linear time but the search problem requires exponential time.
Ilango, in his CCC2020 paper, makes progress in connecting the search and decision complexity for minimizing formulas for any given boolean function. The main result that we'll discuss today is that given an oracle to MFSP (Minimum Formula Size Problem), one can solve Search-MFSP in time polynomial in the length N of the input (which is the truth table of the function f) and the number t of "near-optimal" formulas for f, in time O(poly(N,t)). While this quantity t is not well-understood, we will see how this result gives us a deterministic O(2^{N/loglog(N)})-time oracle algorithm for solving Search-MFSP on all but a o(1) fraction of instances.
