• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>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

机译：低音HyperCube切片的低影响功能取决于几个坐标

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

摘要

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].
机译：在Boolean函数分析的一个经典结果之一是Friedgut〜Cite {Fri98}的结果，指出低影响的HyperCube上的布尔函数是Juntas，其功能由少数坐标确定。虽然该结果也扩展到产品分布，但在非产品分布的情况下，并不多。我们将此结果概括为Boolean Cube的切片。一片布尔立方体是带有一些固定汉明重量的绳子集。在此设置中，我们定义了影响的概念，并确定在这些域上的功能的自然正交基础。我们基本上遵循统一分配案例的证据，但建立以便这样做是非常非暴力的。所使用的主要技术是由对称组的表示理论的幼小表的组合学，以及由于O'Donnell和Wimmer Owimmer因o'Donnell和Wimmer Owimmer而在布尔超立方体的切片中的应用：[OW09]。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号