High Dimensional Expanders and Property Testing

2013/12/09 by Tali Kaufman, Alexander Lubotzky, Kaufman, Tali +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1312.2367

openalex publication_date 2013/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the high dimensional expansion property as defined by Gromov, Linial and Meshulam, for simplicial complexes is a form of testability. Namely, a simplicial complex is a high dimensional expander iff a suitable property is testable. Using this connection, we derive several testability results.

Cited by

• Spectral radius of simplicial complexes without holes

Related

• Property testing and expansion in cubical complexes
• High dimensional expansion implies amplified local testability
• Constant Degree Direct Product Testers with Small Soundness
• New High Dimensional Expanders from Covers
• Characterizing Direct Product Testing via Coboundary Expansion