1. The coordinated dictatorship test
Recall our dictatorship test. It depends on a parameter . Choose uniformly at random vectors , , (meaning independant with ) and .
Then query , and and accept iff . Completeness is and soundness is .
1.1. First attempt
A coordinated dictatorship test is designed to recognize wether two boolean functions and are dictators and are the same dictator. Our first attempt was as follows. Given the same distribution on as above, query , and and accept iff .
Completeness is and soundness is , meaning that
This is not sufficient, since we want soundness . And our analysis assumed .
1.2. Introducing a random decoder
Use the idea of randomized decoding. Now our coordinated dictatorship test has three parameters , and . Data are two boolean functions and and a permutation of . We want a test that makes queries to , , and detects wether , with . The test involves a random decoder , i.e. a random map from boolean functions to indices in .
Completeness: If and with , then .
Soundness: If , then
Last time, we described a random decoder such that the corresponding coordinated dictatorship test satisfies the above requirement with .
2. Reduction from Unique games to GAP LIN
A Unique games instance is the data of a graph, a distribution over edges, and for each edge , a bijection . Say edge is satisfied by an assignment if . In other words, the value of assignment on instance is
The gap problem -UG is to distinguish between
- YES : such that ;
- NO : , .
Subhash Khot’s Unique Games Conjecture states that , , such that -UG is NP-hard.
Assuming UGC, we want to show hardness of -GAP LIN. So given an instance of -UG, we shall construct an instance of -GAP LIN, in such a way that YES instances are mapped to YES instances and NO instances are mapped to NO instances.
2.2. The gadget
There will be variables for every vertex in our LIN instance. We view these boolean variables as the values of some (variable) boolean function . Whence the (a bit strange) notation for these variables.
We define a distribution over equations as follows. Pick an edge at random. Pick at random as in the test. Generate equation . It is indeed a linear equation over with three variables.
Assume that is a YES case, i.e. that there exists an assignment with . Define an assigment of as follows. For all , all boolean functions ,
In other words, we decide that is a dictator at coordinate . With probability over the choice of edge , . In this case, the probability, over equations, that the test accepts, is . So .
Assume that is not a NO case, i.e. there exists an assignment such that . We must construct an assignment with . We choose random decoding parameters . gives us a function for every vertex . Generate randomly by applying the random decoding procedure to , i.e. we set
By assumption, on average over edges , satisfies the random equation
with probability . So, by Markov inequality, for at least fraction of edges , the test accepts with probability . The soundness of the coordinated dictatorship test implies that for these edges, . So the expected fraction of edges satisfied by is . So there is an assignment such that . I.e. is not a NO instance of Unique games.
The UGC-inapproximability bound obtained is optimal. Indeed, a random assignment of variables solves any LIN instance with probability . More generally, Uri Zwick proved (by constructing SDPs) that all -variable constraint satisfaction problems admit -approximations.
3. NP-hardness of approximating LIN
This is Johan Håstad’s 1998 theorem.
3.1. Black box: hardness of LABEL COVER
We start from LABEL COVER. Instances are directed graphs, for each edge, a constraint (which need not be ). An assignment is a -valued function on vertices. An edge is satisfied by if . The value of assignment is
The gap problem -LABEL COVER amounts to deciding between
- YES : such that ;
- NO : , .
It follows from the work of many people (initially, the PCP and parallel repetition theorems, more direct proofs have been proposed recently by Moshkovitz and Raz, Dinur and Harsha) that for all , such that -LABEL COVER is NP-hard.
3.2. The test
To have a reduction from LABEL COVER to LIN, we need an improved test and decoding procedure, since the constraint is not any more.
Let be an arbitrary map.
Let be the following test. The data are two Boolean functions and . The test is designed to detect pairs of dictators which correspond to the same coordinate. So denote by where .
Choose uniformly at random vectors , , and . Then query , and and accept iff .
where is the set of coordinates such that is odd.
Proof: Let . Then
It follows that completeness is . Also, if , then for some odd size , is large.
and play unsymmetric roles, but this does not matter. The decoding algorithm will be applied first to and , and then to and .
Now among all with of odd size , pick at random with probability (discard large sets) and pick uniformly at random. Among all with of size and , pick at random with probability (discard large sets) and pick uniformly at random.
and this leads to
So the probability that is chosen for and is chosen for is is . Since is odd, is not empty, so the probability that the further choices and satisfy is . This gives an upper bound on soundness.
3.5. Reduction from -LABEL COVER to LIN
Not essentially different from previous reduction.
Riikka Kangaslampi: seems to play no role. Answer: that is right. It merely must be taken large to have NP-completeness.
Irit Dinur; Prahladh Harsha; Composition of low-error 2-query PCPs using decodable PCPs. FOCS 2009.
Dana Moshkovitz; Ran Raz; Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. Journal of Computational Complexity (to appear).
Uri Zwick; Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. Proc. of 9th SODA (1998), 201–210.