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.
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.
A recent press release gives some information on how censorship is performed in the Chinese version of Skype; the results are discussed in more detail in a paper by Jeffrey Knockels, Jed Crandall and myself. Currently, a significant portion of Internet censorship is keyword based: any content that contains a keyword that is on some blacklist is censored. Countries that perform keyword censorship generally try to hide these blacklists, probably both for political reasons and to make it difficult to evade censorship by using neologisms: new words that have the same meaning but are not on the blacklist.
In some peer-to-peer applications, this censorship is done on the client side, so there is a subroutine in, e.g. Skype chat, that checks if an outgoing message contains a keyword on the blacklist. If you are the censor and you don’t care about revealing the blacklist, then there are techniques for doing this in an efficient manner (hint: FSA’s). However, it’s an interesting (but evil) theoretical problem to think about how to efficiently do keyword censorship if you are also trying to also hide the blacklist. In particular, if you want to hide it from someone who may be running your executable in a debugger. Hint: the Chinese Skype program did it incorrectly and that’s why we were able to decrypt their blacklist!