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

文章基本信息

  • 标题:A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
  • 本地全文:下载
  • 作者:Andris Ambainis ; Krisjanis Prusis
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity. Previously the best known lower bound was C1(f)2s0(f)bs0(f), achieved by Kenyon and Kutin. We improve this to C1(f)2s0(f)3bs0(f). While this improvement is only by a constant factor, this is quite important, as it precludes achieving a superquadratic separation between bs(f) and s(f) by iterating functions which reach this bound. In addition, this bound is tight, as it matches the construction of Ambainis and Sun up to an additive constant.

  • 关键词:block sensitivity; Boolean Functions; certificate complexity; Sensitivity
国家哲学社会科学文献中心版权所有