id: 06080103
dt: a
an: 06080103
au: Musatov, Daniil
ti: Space-bounded Kolmogorov extractors.
so: Hirsch, Edward A. (ed.) et al., Computer science ‒ theory and
    applications. 7th international computer science symposium in Russia,
    CSR 2012, Nizhny Novgorod, Russia, July 3‒7, 2012. Proceedings.
    Berlin: Springer (ISBN 978-3-642-30641-9/pbk). Lecture Notes in
    Computer Science 7353, 266-277 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-30642-6_25
ab: Summary: 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.
rv: