Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-182 | 22nd December 2014 18:34

Direct Product Testing With Nearly Identical Sets


Authors: Dana Moshkovitz
Publication: 22nd December 2014 18:36
Downloads: 1561


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,
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.


Comment #1 to TR14-182 | 10th May 2016 14:55

A simple reduction between different intersection sizes for direct product tests

Comment #1
Authors: Irit Dinur
Accepted on: 10th May 2016 14:55
Downloads: 1222


We 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].

ISSN 1433-8092 | Imprint