Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors

We prove a strong Symmetry of Information relation for random strings (in the sense of Kolmogorov complexity) and establish tight bounds on the amount on nonuniformity that is necessary for extracting a string with randomness rate 1 from a single source of randomness. More precisely, as instantiations of more general results, we show: · For all n-bit random strings x and y, x is random conditioned by y if and only if y is random conditioned by x; · While O(1) amount of advice regarding the source is not enough for extracting a string with randomness rate 1 from a source string with constant random rate, ω(1) amount of advice is. The proofs use Kolmogorov extractors as the main technical device.