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

文章基本信息

  • 标题:Lattice Variant of the Sensitivity Conjecture
  • 本地全文:下载
  • 作者:Meena Boppana
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The Sensitivity Conjecture, posed in 1994, states that the fundamental measures known as the sensitivity and block sensitivity of a Boolean function f, s(f) and bs(f) respectively, are polynomially related. It is known that bs(f) is polynomially related to important measures in computer science including the decision-tree depth, polynomial degree, and parallel RAM computation time of f, but little is known how the sensitivity compares; the separation between s(f) and bs(f) is at least quadratic and at most exponential. We analyze a promising variant by Aaronson that implies the Sensitivity Conjecture, stating that for all two-colorings of the d-dimensional lattice Zd, d and the sensitivity s(C) are polynomially related, where s(C) is the maximum number of differently-colored neighbors of a point. We construct a coloring with the largest known separation between d and s(C), in which d=O(s(C)2), and demonstrate that it is optimal for a large class of colorings. We also give a reverse reduction from the Lattice Variant to the Sensitivity Conjecture, and using this prove the first non-constant lower bound on s(C). These results indicate that the Lattice Variant can help further the limited progress on the Sensitivity Conjecture.

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