On Circuit Lower Bounds from Derandomization
On Circuit Lower Bounds from Derandomization
复制标题
论去随机化的电路下界
DOI：
10.4086/toc.2011.v007a012
复制
发表时间：
2011
影响因子：
1
通讯作者：
D. Melkebeek
中科院分区：
文献类型：
--
作者：
S. Aaronson;D. Melkebeek
我们提出了 Kabanets 和 Impagliazzo (2004) 结果的替代证明，即去随机化多项式恒等测试意味着电路下界。我们的证明比原来的论证更简单，规模更好，并且产生了更强的结果。
We present an alternate proof of the result by Kabanets and Impagliazzo (2004) that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.