Consider the following problem. We're given a circuit $C$ with $n$ binary inputs and $n$ binary outputs, computing some boolean function $f_C : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$. We assume for simplicity that $C$ only contains binary AND/OR gates, except for the output gates that can be OR gates of unbounded fan-in. We want to ensure that $C$ is 'disruption-resistant' in the sense that modifying a small number of gates does not change the output. Formally, fix an integer $k$ and a circuit $C$. Call a '$k$-disruption' of $C$ a circuit $C'$ obtained from $C$ by modifying $k$ gates, except for output gates. Say that $C$ is '$k$-resistant' if, for any $k$-disruption $C'$ of $C$, it holds that $f_{C'} = f_C$, i.e. the two circuits compute the same function.
Consider the function $\chi_k : \mathbb{Z}_2^k \rightarrow \mathbb{Z}_2^k$ such that $\chi_k(x) = y$ with $y_j = 1 \Leftrightarrow \sum_{i = 1}^{k} x_i \geq j$. Given two tuples $u,v \in \mathbb{Z}_2^k$, say that $v$ is an $l$-perturbation of $u$ if $d_H(u,v) \leq l$. Consider the following question: given $l < k$, can we find a circuit $X_{k,l}$ such that for each $k$-disruption $C$ of $X_{k,l}$, for each $u \in \mathbb{Z}_2^k$, there is an $l$-perturbation $v$ of $u$ such that $f_C(u) = \chi_k(v)$? That is to say, $C$ would count the one-entries of $u$ up to some additive error $l$.
Suppose that we can find such a circuit $X_{4k,k}$ for any integer $k$. We can then solve the first problem using replication as follows. Take $4k$ copies $C_1,\ldots,C_{4k}$ of the given circuit $C$, and let gate $g_{i,j}$ be the $j$th output gate of $C_i$. For each $j \in [n]$, insert a copy of the circuit $X_{4k,k}$ with input connected to the gates $g_{1,j},\ldots,g_{4k,j}$, and with output gates labeled by $h_{1,j},\ldots,h_{4k,j}$. Finally, let the output gate for the $i$th bit be an OR of the outputs $h_{2k-1,i},\ldots,h_{4k,i}$. Let $\Gamma$ denote the resulting circuit. It is then easy to see that for any $k$-disruption $C'$ of $\Gamma$, there are at least $3k$ circuits $C_i$ that are not affected. Thus, if we consider a fixed input $x$, for each $i$th output bit the following holds: if the gates $g_{1,i},\ldots,g_{4k,i}$ evaluate to a constant tuple $t$ in $\Gamma$ and to a tuple $t'$ in $C'$, then $t'$ is a $k$-perturbation of $t$, and by definition of the circuit $X_{4k,k}$ it then computes a value $\chi_k(t'')$ with $t''$ a $2k$-perturbation of $t$. As this circuit has $4k$ outputs it follows that taking the OR of the last $2k+1$ values yields the desired result.
It it thus desirable to construct a circuit $X_{k,l}$ fullfilling the above requirements. I'm working on it but I welcome ideas or advice you may have.
