Language compression and pseudorandom generators
From MaRDI portal
Publication:813317
DOI10.1007/s00037-005-0199-5zbMath1085.68040OpenAlexW2155949379MaRDI QIDQ813317
Harry Buhrman, Dieter van Melkebeek, Troy Lee
Publication date: 8 February 2006
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-005-0199-5
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Reconstructive dispersers and hitting set generators ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Variations on Muchnik's conditional complexity theorem ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ On the Optimal Compression of Sets in PSPACE ⋮ On optimal language compression for sets in PSPACE/poly
