# Correlation between noise resilience and output distribution of Boolean circuits

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, 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 and A. Mozeika, D. Saad, On reliable computation by noisy random Boolean formulas 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.

• 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 Sep 11 '19 at 20:20