• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates
【24h】

Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates

机译：依赖于少量坐标的布尔超立方体切片上的低影响函数

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

One of the classic results in analysis of Boolean functions is a result of Friedgut~cite{Fri98} that states that Boolean functions over the hypercube of low influence are approximately juntas, functions which are determined by few coordinates. While this result has also been extended to product distributions, not much is known in the case of nonproduct distributions. We generalize this result to slices of the Boolean cube. A slice of the Boolean cube is the set of strings with some fixed Hamming weight. In this setting, we define the notion of influence and determine a natural orthogonal basis for functions over these domains. We essentially follow the proof for the uniform distribution case, but the set up in order to do so is highly nontrivial. The main techniques used are combinatorics of Young tableaux motivated by the representation theory of the symmetric group along with an application of hypercontractivity in slices of the Boolean hypercube due to O'Donnell and Wimmer OWimmer:[OW09].
机译：布尔函数分析的经典结果之一是Friedgut〜cite {Fri98}的结果，该结果指出，低影响超立方体上的布尔函数近似为junta，这些函数由很少的坐标确定。虽然此结果也已扩展到产品分销，但在非产品分销的情况下知之甚少。我们将此结果推广到布尔立方体的切片。布尔立方体的一个切片是一组具有固定汉明权重的字符串。在这种情况下，我们定义了影响的概念，并为这些域上的函数确定了自然的正交基础。我们本质上遵循均匀分布情况的证明，但为此目的进行的设置非常重要。由于O'Donnell和Wimmer OWimmer，[OW09]，使用的主要技术是受对称组表示理论启发的Young tableaux组合技术，以及超约束性在布尔超立方体切片中的应用。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号