1. Estimate on soundness of dictatorship test, continued
Recall our dictatorship test: Pick and uniformly at random, independantly. Let , and uniform in . Accept iff .
We have shown last time that if , then
Observe that for the dictator , only gives a nonzero coefficient, so , as required for completeness.
For soundness, assume that . Then
Since , there exists with odd such that . Think of as much smaller than . Since , This implies that , i.e. there exists such that , and
In particular, most of the time, .
Remark 1 Let , then .
Indeed, . It looks bad ( passes the test with high probability). It is not so bad, since is dominated by a few coordinates.
How can one express that a coordinate plays a prominent role in a boolean function ?
2. Random decoding
We describe a random procedure that associates a coordinate to a boolean function, i.e. a -valued random variable. Consider subsets of odd size, relatively small, i.e. . Choose a subset of with probability , discard it and replace it by if it is even or large. Then take unformly at random in .
We try to test simultaneously two functions, decide wether they are dictators with the same variable.
Theorem 1 Let , be distinct functions. Take , uniformly at random in , unformly at random in , and . Accept iff .
The completeness of the test is .
The soundness of the test is . Furthermore, if and denote the random decoding variables associated to and respectively, then
independently on .
Proof: A similar calculation as before gives
If , then , and we get
since is the probability that be selected by both the and the -decoder, and is the probability that both decoders select the same coordinate.
Remark 2 We have played with a weird looking code: a number between and is coded by the corresponding dictator function in variables. It sounds terrible as a code (although it has been used during one of the first space missions, due to its suitability to analogic treatment), but it is very easy to decode. This is what we have used.
3. From decoding to hardness of approximation
We tested wether . Similarly, for any permutation , we can test wether .
Reduction from a unique games (with labels) instance requires constructing an instance of ELIN, i.e. a distribution over linear equations in -variables. To every variable of and , we associate a variable of denoted by (may look like a strange notation…). To define the distribution on equations, pick an edge of at random. Pick , uniformly at random in , uniformly at random in , and view
as an equation with unknowns , and .
What we have to show next time is
Completeness: If there exists an assignment for satisfying more than fraction of constraints, then there exists an assignment for satisfying more than fraction of constraints.
Soundness: If there exists an assignment for satisfying more than fraction of constraints, then there exists an assignment for satisfying more than fraction of constraints.