On generating independent random strings

DOI10.1007/978-3-642-03073-4_51MaRDI QIDQ3576088zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 28 July 2010

Published in Mathematical Theory and Computational Practice (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.3889

zbMATH Keywords

independent stringsKolmogorov complexityrandom stringsrandomness extraction

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: It is shown that from two strings that are partially random and independent (in the sense of Kolmogorov complexity) it is possible to effectively construct polynomially many strings that are random and pairwise independent. If the two initial strings are random, then the above task can be performed in polynomial time. It is also possible to construct in polynomial time a random string, from two strings that have constant randomness rate.

Recommendations

• Generating Kolmogorov random strings from sources with limited independence
• Sets of K-independent strings
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Counting dependent and independent strings
• Power from Random Strings

Cites work

• A 2-Source Almost-Extractor for Linear Entropy
• Algorithmically Independent Sequences
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Extractors with weak random seeds
• Independent minimum length programs to translate between given strings
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(7)

• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
• Random number generation: A combinatorial approach
• Generating Kolmogorov random strings from sources with limited independence
• Sets of K-independent strings
• Counting dependent and independent strings
• Extracting Kolmogorov complexity with applications to dimension zero-one laws
• Algorithmically independent sequences

This page was built for publication: On generating independent random strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576088)