...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >On the Complexity of Hardness Amplification
【24h】

On the Complexity of Hardness Amplification

机译：论硬度放大的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

For deltaisin(0,1) and k,n isinN, we study the task of transforming a hard function f: {0,1}nrarr {0,1}, with which any small circuit disagrees on (1-delta)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1-deltak)/2 fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size 2o(k 1/d) or by a nondeterministic circuit of size o(k/logk) (and arbitrary depth) for any deltaisin(0,1). This extends the result of Viola, which only works when (1-delta)/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f', even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with Omega(klog(1/delta)) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1-delta)/2=2- n. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.
机译：对于deltaisin（0,1）和 k ， n isinN，我们研究了转换硬函数 f 的任务：{0,1} n rarr {0,1}，任何小电路在输入的（1-delta）/ 2小数部分上都不一致，因此变成了更难的函数 f '，任何小电路在输入的（1-delta k ）/ 2分数上都不相同。首先，我们表明，当以某种黑盒方式进行这种硬度放大时，必须要求很高的复杂性。特别是，它不能通过深度 d 和尺寸2 o （ k 1 / d ）或大小为 o （ k / log k ）（和任意深度）的不确定电路（对于任意deltaisin（0,1））。这扩展了Viola的结果，只有在（1-delta）/ 2足够小时，该结果才起作用。此外，我们表明，即使不对扩增程序的复杂性进行任何限制，这种黑匣子硬度扩增在以下意义上也必须固有地是不均匀的。为了保证结果函数 f '的硬度，即使在统一的机器上，也必须从函数 f 开始，这对于使用Omega（ k log（1 / delta））位建议。这扩展了Trevisan和Vadhan的结果，后者仅解决了（1-delta）/ 2 = 2 - n 的情况。最后，我们从硬函数中得出伪随机生成器（PRG）的任何黑盒构造的相似下限。为了证明我们的结果，我们将硬度放大和PRG构造的任务分别链接到某种类型的减少错误的代码，然后为这些代码确定下界，希望对编码理论和复杂性理论都感兴趣。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号