Universal conditional coding in space-bounded framework

An. Muchnik's theorem (2002) states that among all programs that output $a$ on input $b$ and have length close to optimal there exists one that is simple conditional on $a$. Moreover, for a polynomial set $b_1$,...,$b_m$ there exists a string $p$ that is simple conditional on $a$ and such that its $K(a|b_i)$-bit prefix describes $a$ conditional on $b_i$. It would be shown that for space-bounded complexity an analogous theorem holds not only for a polynomial set of $b_i$ but for all strings $b$ of polynomial length. The proof employs the "naive derandomization" technique: a random object with some combinatorial properties is replaced by a pseudo-random one obtained by Nisan-Wigderson pseudo-random generator.