文章基本信息

标题：Testing Odd Direct Sums Using High Dimensional Expanders
本地全文：下载
作者：Roy Gotlib ; Tali Kaufman
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-20
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.50
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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, 2014] 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.
关键词：High Dimensional Expanders; Property Testing; Direct Sum