Title | ||
---|---|---|
Near Coverings and Cosystolic Expansion - an example of topological property testing. |
Abstract | ||
---|---|---|
We study the stability of covers of simplicial complexes. Given a map $f:Y\to X$ that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of $X$? Complexes $X$ for which this holds are called cover-stable. We show that this is equivalent to $X$ being a cosystolic expander with respect to non-abelian coefficients. This gives a new combinatorial-topological interpretation to cosystolic expansion which is a well studied notion of high dimensional expansion. As an example, we show that the $2$-dimensional spherical building $A_{3}(\mathbb{F}_q)$ is cover-stable. We view this work as a possibly first example of "topological property testing", where one is interested in studying stability of a topological notion that is naturally defined by local conditions. |
Year | Venue | DocType |
---|---|---|
2019 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
26 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Irit Dinur | 1 | 1187 | 85.67 |
Roy Meshulam | 2 | 0 | 1.69 |