Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-089 | 11th May 2017 23:32

High dimensional expanders imply agreement expanders


Authors: Irit Dinur, Tali Kaufman
Publication: 11th May 2017 23:32
Downloads: 608


We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is *linear* in the size of the universe.

Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree tests such as line vs. line and plane vs. plane.

For a generic hypergraph, we introduce the notion of agreement expansion, which captures the usefulness of the hypergraph for an agreement test.
We show that explicit bounded degree agreement expanders exist, based on Ramanujan complexes.

~~ to Oded Goldreich, with love and admiration, on the occasion of his 60th birthday ~~

ISSN 1433-8092 | Imprint