High Dimensional Expanders Imply Agreement Expanders
Authors:
- Irit DinurIDIrit Dinur
- Tali KaufmanTKTali Kaufman
- 1 October 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 974-985
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Ramanujan Complexes and Bounded Degree Topological Expanders2014
- Direct Product Testing2014
- Derandomized Parallel Repetition via Structured PCPscomputational complexity, 2011
- Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic IsoperimetryGeometric and Functional Analysis, 2010
- New direct-product testers and 2-query PCPs2009
- Locally Testing Direct Product in the Low Error Range2008
- Homological Connectivity Of Random 2-ComplexesCombinatorica, 2006
- Assignment Testers: Towards a Combinatorial Proof of the PCP TheoremSIAM Journal on Computing, 2006
- A combinatorial consistency lemma with application to proving the PCP theorem1997
- Impossibility results for recycling random bits in two-prover proof systems1995