Let $f$ be a boolean function on $n$ variables - say we want to find the smallest circuit $C$ where $C(x)=f(x)$ for all but an $\epsilon$ fraction of inputs $x \in \{0,1\}^n$. What is known about the complexity of this problem?
The following is what I've found in the literature.
The case $\epsilon=0$, i.e. $C$ is the smallest circuit that represents $f$ exactly, is the MCSP (minimum circuit size problem). Its complexity is an interesting open question. There are some results around the complexity of an approximation version of MCSP$^*$, but the approximation factor is on the size of the circuit not the degree to which it matches $f$.
There are also some interesting results for the case where $\epsilon$ is arbitrary but $C$ is restricted to DNF formulae, i.e. depth-2 circuits$^{**}$. That paper shows that almost all boolean functions require large DNFs to even be approximated.
However I wasn't able to find anything for the general case of arbitrary $C$ and $\epsilon$. Is anything known about the complexity of this problem?
