**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 1Let , 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 1Let , 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 2We 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.

** References **