首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Direct sum testing - the general case
  • 本地全文:下载
  • 作者:Irit Dinur ; Konstantin Golubev
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-11
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    A function f:[n_1] x ... x [n_d]-->F is a direct sum if it is of the form f(a_1,...,a_d) = f_1(a_1) + ... + f_d (a_d) (mod 2) for some d functions f_i:[n_i]-->F_i for all i=1,...,d. We present a 4-query test which distinguishes between direct sums and functions that are far from them. The test relies on the BLR linearity test (Blum, Luby, Rubinfeld, 1993) and on an agreement test which slightly generalizes the direct product test.In multiplicative {+1,-1} notation, our result reads as follows. A d-dimensional tensor with {+1,-1} entries is called a tensor product if it is a tensor product of d vectors with {+1,-1} entries, or equivalently, if it is of rank 1. The presented tests can be read as tests for distinguishing between tensor products and tensors that are far from being tensor products.We also present a different test, which queries the function at most (d+2) times, but is easier to analyze.

  • 关键词:direct product testing ; direct sum
国家哲学社会科学文献中心版权所有