Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-175 | 4th December 2022 15:25

Derandomization Under Different Resource Constraints

RSS-Feed




Revision #1
Authors: Samuel Epstein
Accepted on: 4th December 2022 15:25
Downloads: 54
Keywords: 


Abstract:

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.


Paper:

TR22-175 | 16th November 2022 19:02

Derandomization Under Different Resource Constraints





TR22-175
Authors: Samuel Epstein
Publication: 4th December 2022 06:19
Downloads: 40
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint