High Dimensional Expanders Imply Agreement Expanders

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.

Authors

• Irit Dinur
• Tali Kaufman

Keywords

• Buildings
• Graph theory
• Computer science
• Convergence
• Eigenvalues and eigenfunctions
• Skeleton
• Electronic mail
• High-dimensional
• Direct Test
• Direct Product
• Hypergraph
• Eigenvalues
• Undirected
• Random Walk
• Properties Of Complexes
• Natural Distribution
• Probability 1
• Direct Sum
• Proof Of The Lemma
• Simplicial Complex
• Self-adjoint
• Self-adjoint Operator
• Cohomology
• Number Theory
• Strong Mixing
• Subset Of Pairs
• Expansion Of Type
• Dimensional Complex
• Correct Proportion
• Collection Of Functions
• Random Step
• Space Of Functions
• Local Coefficient
• Local Function
• high dimensional expanders
• agreement tests