...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Small Bias Requires Large Formulas
【24h】

Small Bias Requires Large Formulas

机译：小偏差需要大公式

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

摘要

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on (1) the size of general Boolean formulas, (2) the size of De Morgan formulas, and (3) correlation against small De Morgan formulas apply to small-biased functions. As a consequence, any strongly explicit small-biased generator is subject to the best-known explicit formula lower bounds in all these models.On the other hand, we give a construction of a small-biased function that is tight with respect to lower bound (1) for the relevant range of parameters. We interpret this construction as a natural-type barrier against substantially stronger lower bounds for general formulas.
机译：小偏差函数是随机函数，其真值表的分布是小偏差的。我们证明（1）一般布尔型公式的大小，（2）De Morgan公式的大小和（3）与小型De Morgan公式的相关性的已知显式下界适用于小偏函数。结果，任何强显式小偏置生成器都受所有这些模型中最著名的显式公式下界的限制;另一方面，我们给出了一个相对于下界严格的小偏置函数的构造（1）获取相关参数范围。我们将此构造解释为一种针对通用公式的明显更低的下界的自然类型的障碍。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号