Optimal bounds for single-source Kolmogorov extractors

DOI10.1090/TRAN/7972zbMATH Open1443.03022arXiv1806.05936OpenAlexW2982354992MaRDI QIDQ5217889FDOQ5217889

Matthew Harrison-Trainor, Barbara Csima, Laurent Bienvenu

Publication date: 26 February 2020

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: The rate of randomness (or dimension) of a string $sigma$ is the ratio $C(sigma)/|sigma|$ where $C(sigma)$ is the Kolmogorov complexity of $sigma$. While it is known that a single computable transformation cannot increase the rate of randomness of all sequences, Fortnow, Hitchcock, Pavan, Vinodchandran, and Wang showed that for any $$, there are a finite number of computable transformations such that any string of rate at least $alpha$ is turned into a string of rate at least $$ by one of these transformations. However, their proof only gives very loose bounds on the correspondence between the number of transformations and the increase of rate of randomness one can achieve. By translating this problem to combinatorics on (hyper)graphs, we provide a tight bound, namely: Using $k$ transformations, one can get an increase from rate $alpha$ to any rate $$, and this is optimal.

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

zbMATH Keywords

hypergraphsKolmogorov complexityrandomness extractioneffective packing dimension

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic Randomness and Complexity
• Computability and Randomness
• An introduction to Kolmogorov complexity and its applications
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Independent minimum length programs to translate between given strings
• Constructive dimension and Turing degrees
• Extracting Randomness Using Few Independent Sources
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one

This page was built for publication: Optimal bounds for single-source Kolmogorov extractors

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