# Machinations

Networks of Noisy Gates (Part 4)
October 21, 2011, 5:40 pm
Filed under: Uncategorized | Tags: , ,

In this post, I want to finish up the result that for any function of n inputs, there is a network of O(2^n/n) noisy gates that will compute that function with probability better than 1/2.  Since most functions require O(2^n/n) noise-free gates, this will show that, for most functions, there is at most a constant blowup in gates when all gates are noisy.

Recall from last time that we can build a MUX over 2^x signals with O(2^x) noisy gates.  Using a similar technique, for any set of x inputs, we can build an “All Functions” circuit that computes all 2^(2^x) possible functions of these inputs with O(2^(2^x)) gates. Our result today will make use of both 1) an “All Functions” circuit and 2) a MUX.

The technique is illustrated in the figure below.  Assume we’re trying to compute a function f of n inputs.  Let a = log (n-log n) Basically, we send a of the inputs the “All Functions” circuit and we send n-a of the inputs to the MUX.  The MUX selects, based on the first n-a inputs, the exact function of the remaining a inputs that determines the function f over all n inputs.  The MUX selects 1 of 2^(n-a) such “completion functions”.

The beautiful thing here is that both the MUX and the “All Functions” circuit require only O(2^n/n) gates.  Thus, this clever combination of both types of circuits has saved us a factor of n in the total number of noisy gates required.