• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Fourier Concentration from Shrinkage
【24h】

Fourier Concentration from Shrinkage

机译：傅里叶浓度来自收缩

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

摘要

For Boolean functions computed by de Morgan formulas of sub quadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on "small-degree" coefficients. For a Boolean function f: {0, 1}^nto {1, -1} computable by a de Morgan formula of size s, we show that [ sum_{Asubseteq [n]:, |A|>s^{1/Gamma + epsilon}} hat{f}(A)^2 leq exp(-s^{epsilon/3}), ] where Gamma is the shrinkage exponent for the corresponding class of formulas: Gamma=2 for de Morgan formulas, and Gamma=1/log_2(sqrt{5}-1)approx 3.27 for read-once de Morgan formulas. We prove that this Fourier concentration is essentially optimal. As an application, we get that sub quadratic-size de Morgan formulas have negligible correlation with parity, and are learnable under the uniform distribution, and also lossily compressible, in sub exponential time. Finally, we establish the tight Theta(s^{1/Gamma}) bound on the average sensitivity of read-once formulas of size s, this mirrors the known tight bound Theta(sqrt{s}) on the average sensitivity of general de Morgan formulas of size s.
机译：对于由De Morgan公式计算的Boolean函数，由Sub二次尺寸或阅读摩根公式计算，我们证明了“小程度”系数上的傅里叶质量的急剧浓度。对于一个布尔函数f：{0，1} ^ no {1，-1}由de摩根公式计算的大小s，我们展示了[sum_ {asubseteq [n]：，| a |> s ^ {1 /伽马+ epsilon}}帽子{f}（a）^ 2 leq exp（-s ^ {epsilon / 3}），其中伽玛是相应类公式的收缩指数：伽马= 2用于de摩根公式， GAMMA = 1 / log_2（SQRT {5} -1）约3.27用于阅读默诺摩根公式。我们证明这种傅立叶浓度基本上是最佳的。作为申请，我们得到了亚二次尺寸的摩根公式的相关性与平价可忽略不计，并且在均匀分布下可以在均匀分布下进行，并且在子指数时间内造成可压缩。最后，我们建立了在尺寸S的读取式公式的平均敏感度的紧密θ（s ^ {1 / gamma}），这反映了已知的紧密绑定的θ（sqrt {s}）普通德的平均敏感性摩根公式的规模。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号