Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors

Details Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors

2011-03-29

arxiv.org/abs/1103.5669v1

Computer Science

Computational Complexity

To appear in the proceedings of CCC 2011

Scientific paper

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: (1) 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, and (2) 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, \omega(1) amount of advice is. The proofs use Kolmogorov extractors as the main technical device.

Affiliated with

Also associated with

No associations

Rating

Symmetry of information and bounds on nonuniform randomness extraction via 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 Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163556