• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Shrinkage of De Morgan Formulae by Spectral Techniques
【24h】

Shrinkage of De Morgan Formulae by Spectral Techniques

机译：光谱技术对De Morgan公式的收缩

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

摘要

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is 2. Namely, we show that for any Boolean function f : {0,1}n → {0,1}, setting each variable out of x1,,xn with probability 1 -- p to a randomly chosen constant, reduces the expected formula size of the function by a factor of O(p2). This result is tight and improves the work of Håstad [SIAM J. C., 1998] by removing logarithmic factors. As a consequence of our results, the function defined by Andreev [MUMB., 1987], A : {0,1}n → {0,1}, which is in P, has formula size at least Ω(n3/log2 n log3 log n). This lower bound is tight (for the function A) up to the log3log n factor, and is the best known lower bound for functions in P. In addition, we strengthen the average-case hardness result of Komargodski et al., we show that the functions defined by Komargodski et al., hr: {0,1}n → {0,1}, which are also in P, cannot be computed correctly on a fraction greater than 1/2 + 2 -- r of the inputs, by De Morgan formulae of size at most n3/r2poly log n, for any parameter r ≤ n{1/3}. The proof relies on a result from quantum query complexity by Laplante et al. [CC, 2006], Hϕyer et al. [STOC, 2007] and Reichardt [SODA, 2011]: for any Boolean function f, Q2(f) &le, O(√L(f)), where Q2(f) is the bounded-error quantum query complexity of f, and L(f) is the minimal size De Morgan formla computing f.
机译：我们提供了一个新的改进的证明，即De Morgan公式的收缩指数为2。即，我们证明了对于任何布尔函数f：{0,1} n→{0,1}，将每个变量设置为x1 ,,概率为1-p的xn为随机选择的常数，将函数的预期公式大小减小了O（p2）。这个结果很严格，并且通过消除对数因子改善了Håstad[SIAM J. C.，1998]的工作。结果表明，由Andreev [MUMB。，1987]定义的函数A：{0,1} n→{0,1}在P中，其公式大小至少为Ω（n3 / log2 n log3 log n）。这个下界是紧密的（对于函数A），直到log3log n因子为止，并且是P中函数最著名的下界。此外，我们加强了Komargodski等人的平均情况下的硬度结果，我们发现Komargodski等人定义的函数hr：{0,1} n→{0,1}（也位于P中）无法在大于输入的1/2 + 2-r的分数上正确计算对于任何参数r≤n {1/3}，根据De Morgan的公式，大小最大为n3 / r2poly log n。该证明依赖于Laplante等人的量子查询复杂性结果。 [CC，2006]，Hϕyer等。 [STOC，2007]和Reichardt [SODA，2011]：对于任何布尔函数f，Q2（f）＆le，O（√L（f）），其中Q2（f）是f的有界误差量子查询复杂度， L（f）是De Morgan formla计算f的最小大小。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号