Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-124 | 28th August 2019 02:58

Testing Odd Direct Sums Using High Dimensional Expanders


Authors: Roy Gotlib, Tali Kaufman
Publication: 17th September 2019 03:04
Downloads: 593


In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.
Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result.

The classical $k$-direct-sum problem applies to the complete complex; Namely it considers a function defined over all $k$-subsets of some $n$ sized universe. Our result here applies to any collection of $k$-subsets of an $n$-universe, assuming this collection of subsets forms a high dimensional expander.

ISSN 1433-8092 | Imprint