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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy