ECCC-Report TR14-182https://eccc.weizmann.ac.il/report/2014/182Comments and Revisions published for TR14-182en-usTue, 10 May 2016 14:55:24 +0300
Comment 1
| A simple reduction between different intersection sizes for direct product tests |
Irit Dinur
https://eccc.weizmann.ac.il/report/2014/182#comment1We point out a simple reduction between different intersection sizes in the setting of direct product testing. This reduction allows to deduce the main theorem in [TR14-182] directly from an earlier work on direct product testing [TR13-179].Tue, 10 May 2016 14:55:24 +0300https://eccc.weizmann.ac.il/report/2014/182#comment1
Paper TR14-182
| Direct Product Testing With Nearly Identical Sets |
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2014/182In 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,
and the two subsets intersect in about (1-\delta)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.
Mon, 22 Dec 2014 18:36:05 +0200https://eccc.weizmann.ac.il/report/2014/182