4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Apr 5 '14 at 18:23
  • $\begingroup$ this 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). welcome further Theoretical Computer Science Chat $\endgroup$ – vzn Apr 6 '14 at 3:04
  • $\begingroup$ 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. $\endgroup$ – Peng Zhang Apr 6 '14 at 7:50
  • $\begingroup$ @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. $\endgroup$ – mobius dumpling Apr 7 '14 at 0:57
  • $\begingroup$ PilarLoof, Is the following paper of interest to you? cs.berkeley.edu/~daw/papers/privcirc2-ec06.pdf It's a quite different problem, but somehow vaguely in a similar space. $\endgroup$ – D.W. Apr 8 '14 at 8:57

Your Answer

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

Browse other questions tagged or ask your own question.