# Complexity of approximating boolean functions with circuits

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?

$$*$$ https://ieeexplore.ieee.org/document/8555110

$$**$$ https://doi.org/10.1137/14097402X