Direct Product Testing With Nearly Identical Sets.
Dana Moshkovitz · Electronic colloquium on computational complexity · 2014
In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U , |U | = Θ(n), and the two subsets intersect in about (1 − δ)n elements. We show that if each of the provers provides labels to the n elements it received, and the labels of the two provers agree in the intersection between the subsets with non-negligible probability, then the answers of the provers must correspond to a certain global assignment to the elements of U . While previous results only worked for intersection of size at most n/2, in our model the questions and expected answers of the two provers are nearly identical. This is related to a recent construction of a unique games instance (ECCC TR14-142) where this setup arises at the “outer verifier” level. Our main tool is a hypercontractive bound on the Bernoulli-Laplace model (aka a slice of the Boolean hypercube), from which we can deduce a “small set expansion”-type lemma. We then use ideas from a recent work of the author about “fortification” to reduce the case of large intersection to the already studied case of smaller intersection. 1 Direct Product Testing Let U and R be finite sets, let n ≥ 1 be a natural number, and let 0 ≤ α ≤ 1. We define the following two prover game. The provers are asked to agree on an assignment f : U → R ahead of time. Then a verifier picks at random two subsets S, S′ ⊆ U that intersect in αn elements on average. The verifier sends one subset to each prover. The prover is supposed to report what f(x) is for every x in the subset it got, but is not necessarily truthful. The verifier checks that the assignments reported by the provers agree on the intersection between the two sets. Let S be the family of sized-n subsets of U . Direct Product Test(α): 1. The verifier picks uniformly at random a set S ∈ S. 2. The verifier picks a correlated set S′ ∈ S as follows: for1 k ∼ Poisson((1 − α)n) times, switch an element from S with a uniform element outside of S. ∗[email protected]. Department of Electrical Engineering and Computer Science, MIT. This material is based upon work supported by the National Science Foundation under Grant Number 1218547. Several other choices of a correlated S′ have been used in other works. The one we use follows a convention from probability literature.