Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-182 | 22nd December 2014 18:34

#### Direct Product Testing With Nearly Identical Sets

TR14-182
Authors: Dana Moshkovitz
Publication: 22nd December 2014 18:36
Keywords:

Abstract:

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(s):

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