Networks of Noisy Gates (Part 4)
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.

### Like this:

Like Loading...

**Leave a Comment so far**
Leave a comment