Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
From MaRDI portal
Publication:2254499
DOI10.1007/s00224-012-9432-1zbMath1319.68117arXiv1009.5108OpenAlexW1696733972MaRDI QIDQ2254499
Publication date: 5 February 2015
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.5108
extractorsderandomisationMuchnik's theoremNisan-Wigderson generatorsspace-bounded Kolmogorov complexity
Related Items (7)
Inequalities for space-bounded Kolmogorov complexity ⋮ Short lists for shortest descriptions in short time ⋮ Short lists with short programs in short time ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ On algorithmic statistics for space-bounded algorithms ⋮ On extracting space-bounded Kolmogorov complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Variations on Muchnik's conditional complexity theorem
- Pseudorandom bits for constant depth circuits
- Language compression and pseudorandom generators
- Hardness vs randomness
- Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
- Pseudo-random graphs and bit probe schemes with one-sided error
- Resource-Bounded Kolmogorov Complexity Revisited
- Construction of extractors using pseudo-random generators (extended abstract)
- Space-Bounded Kolmogorov Extractors
- On the Optimal Compression of Sets in PSPACE
- Kakeya Sets, New Mergers, and Old Extractors
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Extractors
- Impossibility of Independence Amplification in Kolmogorov Complexity Theory
- Kolmogorov Complexity and Algorithmic Randomness
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
- Extractors and pseudorandom generators
- Extracting Randomness via Repeated Condensing
- Randomness Buys Depth for Approximate Counting
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Noiseless coding of correlated information sources
- Conditional complexity and codes
This page was built for publication: Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
