Property testing and expansion in cubical complexes
We are given a 2-coloring of the edges of the complete graph. If the number of red edges in triangles is almost always even, then the coloring is approximately defined on vertices. Thus triangles "test" a function on edges to be defined from the vertices.
Replacing triangles by squares, and going up in the dimension, we show that differentials can test properties, as long as the cohomology group is sufficiently well understood.
Joint work with David Garber.
תאריך עדכון אחרון : 11/11/2019