Today I want to talk about an interesting result in Pippenger’s paper “Networks of Noisy Gates” for the Von Neumann noisy gates model. Recall that in this model, each noisy gate fails independently with some fixed probability \epsilon. We are given a circuit to compute a function with m regular gates and our goal is to compute the same function with probability great than 1/2 with as few noisy gates as possible.
In previous posts, we showed that n \log n gates are always sufficient and we showed that for the exclusive-or function, n \log n gates are necessary. This implies that in the worst case, there is a log n blowup in the number of gates required.
There is another result by Pippenger that shows that for *most* boolean functions, only a *constant* blowup is required. Today I want to focus on the first part of this result, which is to show that a multiplexer (MUX) over 2^r signals can be computed with only O(2^r) noisy gates. Recall that a MUX over 2^r signals is a circuit that takes as input both 1) 2^r possible signals; and 2) an r bit selector. The MUX outputs exactly one of the 2^r possible signals, specifically the one that is specified by the r bit selector.
For example, a MUX for r=1 has as input 1) 2 signal bits; and 2) a single selector bit. If the selector bit is 0, the MUX outputs the first signal bit and if the selector bit is 1, the MUX outputs the second selector bit. Let G be a gate that computes the MUX for r=1. Then it’s easy to create a MUX for any r by wiring up O(2^r) copies of G (try it). In particular, a MUX for r requires at least 2^r noise free gates.
Pippenger shows that you can create a MUX for any r using only O(2^r) noisy gates. Clearly this is just a constant blowup over the number of noiseless gates needed to create such a MUX. The construction used to prove this result is sketched in the figure below. See also this pdf: pipp-mux
Note that any boolean function over x inputs can be computed using a MUX, where r=x (the computation is done essentially by table lookup). This means that we can now compute any boolean function over x inputs with O(2^x) noisy gates. It turns out that most boolean functions over x variables require 2^x/x noise-free gates. In my next post, I’ll show how we can shave off this factor of x in the noisy gate world.
Leave a Comment so far
Leave a comment