首页    期刊浏览 2024年12月12日 星期四
登录注册

文章基本信息

  • 标题:Testing Odd Direct Sums Using High Dimensional Expanders
  • 本地全文:下载
  • 作者:Roy Gotlib ; Tali Kaufman
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-21
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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.

  • 关键词:direct sum ; high dimensional expanders ; Property Testing
国家哲学社会科学文献中心版权所有