Space-Bounded Kolmogorov Extractors

Details Space-Bounded Kolmogorov Extractors Space-Bounded Kolmogorov Extractors

2012-03-16

arxiv.org/abs/1203.3674v1

Computer Science

Computational Complexity

12 pages, accepted to CSR2012

Scientific paper

An extractor is a function that receives some randomness and either "improves" it or produces "new" randomness. There are statistical and algorithmical specifications of this notion. We study an algorithmical one called Kolmogorov extractors and modify it to resource-bounded version of Kolmogorov complexity. Following Zimand we prove the existence of such objects with certain parameters. The utilized technique is "naive" derandomization: we replace random constructions employed by Zimand by pseudo-random ones obtained by Nisan-Wigderson generator.

Affiliated with

Also associated with

No associations

Rating

Space-Bounded Kolmogorov Extractors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Space-Bounded Kolmogorov Extractors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-Bounded Kolmogorov Extractors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351645