首页    期刊浏览 2024年10月04日 星期五
登录注册

文章基本信息

  • 标题:An Alternative Proof of an ( k ) Lower Bound for Testing k -linear Boolean Functions
  • 本地全文:下载
  • 作者:Roei Tell
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We provide an alternative proof for a known result stating that ( k ) queries are needed to test k -sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in affine subspaces of the Boolean hypercube. However, we derive our proof from a general result by Linial and Samorodnitsky (2002) that upper bounds the number of vectors with the same Hamming weight in every large affine subspace of the Boolean hypercube. Our line of argument is reminiscent of a technique that is common in communication complexity, and it allows us to derive the lower bound from Linial and Samorodnitsky's result quite easily.

  • 关键词:affine subspaces ; Property Testing
国家哲学社会科学文献中心版权所有