ECCC-Report TR19-124https://eccc.weizmann.ac.il/report/2019/124Comments and Revisions published for TR19-124en-usTue, 17 Sep 2019 03:04:22 +0300
Paper TR19-124
| Testing Odd Direct Sums Using High Dimensional Expanders |
Roy Gotlib,
Tali Kaufman
https://eccc.weizmann.ac.il/report/2019/124In 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.Tue, 17 Sep 2019 03:04:22 +0300https://eccc.weizmann.ac.il/report/2019/124