论文标题
在不同的资源约束下进行降低
Derandomization under Different Resource Constraints
论文作者
论文摘要
我们为EL定理提供了另一个证明。我们显示了代码书的可压缩性与其通信能力之间的权衡。 EL定理的资源有限版本已得到证明。这用于证明资源有限的降低的三个实例。本文支持一般说法，即如果可以通过概率方法证明对象的存在，那么也可以证明其Kolmogorov复杂性的界限。
We provide another proof to the EL Theorem. We show the tradeoff between compressibility of codebooks and their communication capacity. A resource bounded version of the EL Theorem is proven. This is used to prove three instances of resource bounded derandomization. This paper is in support of the general claim that if the existence of an object can be proven with the probabilistic method, then bounds on its Kolmogorov complexity can be proven as well.
