<p>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 <em>does not</em> 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.</p>

<p>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 &lt; 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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-05T18:23:40.337Z
You should reformat this to emphasize your question, in order to clarify how it is on-topic --- not only as a research idea, but an actual *question*, in Theoretical Computer Science.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-06T03:04:49.037Z
[this](http://cstheory.stackexchange.com/questions/17239/k-cnf-k-dnf-conversion-to-minimize-errors) is another/related/somewhat similar angle that measures the similarity of circuits/functions in terms of total "errors", a metric that shows up in groundbreaking circuit lower bounds proofs. one would expect that it could be used to measure "small disruptions/perturbations". another idea, maybe there is some study of "noise" effect in circuits that could be related (there is a highvoted tcs.se question on [noise in CAs](http://cstheory.stackexchange.com/questions/17914/)). welcome further [chat]
vzn
CC BY-SA 3.0
2014-04-06T07:50:58.393Z
This comment may be unrelated. If we view the circuit as an algorithm, "disruption-resistant" emphasizes robustness of algorithms. There are notations of "super solutions in CSP" emphasizes on robustness of solutions.
Peng Zhang
CC BY-SA 3.0
2014-04-07T00:57:14.037Z
@PilarLoof Your question seems interesting but I found it nearly impossible to read it until the end. You might want to simplify the notation, simplify the writing, try to use less quantifiers, and give more motivation.
greg
CC BY-SA 3.0
2014-04-08T08:57:47.353Z
PilarLoof, Is the following paper of interest to you?  http://www.cs.berkeley.edu/~daw/papers/privcirc2-ec06.pdf  It's a quite different problem, but somehow vaguely in a similar space.
D.W.
<circuit-complexity><boolean-functions>
A possible application of TCS to EE: disruption-resistant circuits
NisaiVloot
# A possible application of TCS to EE: disruption-resistant circuits

(Asked by: username_0 on 2014-04-05)

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.

**Tags:** circuit-complexity, boolean-functions
> **Comments:**
> **username_1**: You should reformat this to emphasize your question, in order to clarify how it is on-topic --- not only as a research idea, but an actual *question*, in Theoretical Computer Science.  
> **username_2**: [this](http://cstheory.stackexchange.com/questions/17239/k-cnf-k-dnf-conversion-to-minimize-errors) is another/related/somewhat similar angle that measures the similarity of circuits/functions in terms of total "errors", a metric that shows up in groundbreaking circuit lower bounds proofs. one would expect that it could be used to measure "small disruptions/perturbations". another idea, maybe there is some study of "noise" effect in circuits that could be related (there is a highvoted tcs.se question on [noise in CAs](http://cstheory.stackexchange.com/questions/17914/)). welcome further [chat]  
> **username_3**: This comment may be unrelated. If we view the circuit as an algorithm, "disruption-resistant" emphasizes robustness of algorithms. There are notations of "super solutions in CSP" emphasizes on robustness of solutions.  
> **username_4**: @PilarLoof Your question seems interesting but I found it nearly impossible to read it until the end. You might want to simplify the notation, simplify the writing, try to use less quantifiers, and give more motivation.  
> **username_5**: PilarLoof, Is the following paper of interest to you?  http://www.cs.berkeley.edu/~daw/papers/privcirc2-ec06.pdf  It's a quite different problem, but somehow vaguely in a similar space.  

---

## 0 answers

