<p>I have found some hints on my question in Moshe Looks, <a href="http://www.metacog.org/main.pdf" rel="nofollow noreferrer">Competent Program Evolution</a>, p. 31:</p>
<blockquote>
<p>Most local perturbations of large random formulae have no effect – 96% of them for
arity five, and 91% for arity ten (the drop is a corollary of the increase in the percentage of
unique behaviors in a fixed size sample as the arity increase). This is a consequence of such
formulae typically being highly redundant – e.g., a large formula that computes a tautology
will likely remain a tautology when randomly perturbed (similarly a large subformula which
computes a tautology, etc.).</p>
</blockquote>
<p>More resources would be highly appreciated if you know of any.</p>

CC BY-SA 4.0
2019-08-12T19:55:48.327Z
2019-08-12T19:55:48.327Z
2020-06-17T09:38:08.363Z
cvalkan
<p>Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at least 5) literals, the system of equations becomes too complex to compute, and it's even questionable whether the output distribution of Boolean functions can be reliably approximated. See D. Gardy, <a href="https://dmtcs.episciences.org/3475/pdf." rel="nofollow noreferrer">Random Boolean Expressions</a>, chapter 3.4.3. </p>

<p>Another line of research deals with the question of how robust Boolean circuits are in the presence of noise or faulty gates. See P. Gács, A. Gál, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.424&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates</a> and A. Mozeika, D. Saad, <a href="https://arxiv.org/pdf/1206.4851.pdf" rel="nofollow noreferrer">On reliable computation by noisy random Boolean formulas</a> who explicitly consider random Boolean formulas.</p>

<p>My question is if there is correlation between the probability/frequency of a certain Boolean function and the resilience of a given generating circuit (formula) against noise. In other words, can we estimate (or at least get some bounds on) the probability of a function from the circuit's noise resilience which we could try to measure by causing arbitrary perturbations to gates and see how the resulting function reacts?</p>

<p>My intuition is that circuits representing simple Boolean functions with high probability such as the tautology TRUE or the output of a single literal will tolerate higher noise levels since those circuits have a higher "density" in the space of all possible circuits of a given size.</p>

CC BY-SA 4.0
2019-09-11T20:20:51.147Z
I'd think that such resilience depends not only on how many Boolean ckts compute the same functions, but how closely related those circuits are to one another. Put another way: for a given function, if we look at all the ckts computing it, where do they sit relative to one another in the space of all ckts? For tautologies, you might consider minimal DNF tautologies - ones in which the removal of any single clause makes it not a tautology. Then it's not robust to the removal of one clause, but once you remove say 1% of clauses, you can ask if it's now robust.
Joshua Grochow
<circuits><boolean-formulas>
Correlation between noise resilience and output distribution of Boolean circuits
cvalkan
# Correlation between noise resilience and output distribution of Boolean circuits

(Asked by: username_0 on 2019-08-11)

Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at least 5) literals, the system of equations becomes too complex to compute, and it's even questionable whether the output distribution of Boolean functions can be reliably approximated. See D. Gardy, [Random Boolean Expressions](https://dmtcs.episciences.org/3475/pdf.), chapter 3.4.3.

Another line of research deals with the question of how robust Boolean circuits are in the presence of noise or faulty gates. See P. Gács, A. Gál, [Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.424&rep=rep1&type=pdf) and A. Mozeika, D. Saad, [On reliable computation by noisy random Boolean formulas](https://arxiv.org/pdf/1206.4851.pdf) who explicitly consider random Boolean formulas.

My question is if there is correlation between the probability/frequency of a certain Boolean function and the resilience of a given generating circuit (formula) against noise. In other words, can we estimate (or at least get some bounds on) the probability of a function from the circuit's noise resilience which we could try to measure by causing arbitrary perturbations to gates and see how the resulting function reacts?

My intuition is that circuits representing simple Boolean functions with high probability such as the tautology TRUE or the output of a single literal will tolerate higher noise levels since those circuits have a higher "density" in the space of all possible circuits of a given size.

**Tags:** circuits, boolean-formulas
> **Comments:**
> **username_1**: I'd think that such resilience depends not only on how many Boolean ckts compute the same functions, but how closely related those circuits are to one another. Put another way: for a given function, if we look at all the ckts computing it, where do they sit relative to one another in the space of all ckts? For tautologies, you might consider minimal DNF tautologies - ones in which the removal of any single clause makes it not a tautology. Then it's not robust to the removal of one clause, but once you remove say 1% of clauses, you can ask if it's now robust.  

---

## 1 answers

### Answer by username_0 on 2019-08-12. Score: 1

I have found some hints on my question in Moshe Looks, [Competent Program Evolution](http://www.metacog.org/main.pdf), p. 31:

> Most local perturbations of large random formulae have no effect – 96% of them for
> arity five, and 91% for arity ten (the drop is a corollary of the increase in the percentage of
> unique behaviors in a fixed size sample as the arity increase). This is a consequence of such
> formulae typically being highly redundant – e.g., a large formula that computes a tautology
> will likely remain a tautology when randomly perturbed (similarly a large subformula which
> computes a tautology, etc.).

More resources would be highly appreciated if you know of any.


---

