Abstract
We show two sets of results applying the theory of extractors to resource-bounded Kolmogorov complexity:
-
- Most strings in easy sets have nearly optimal polynomial-time CD complexity. This extends work of Sipser [Sip83] and Buhrman and Fortnow [BF97].
-
- We use extractors to extract the randomness of strings. In particular we show how to get from an arbitrary string, an incompressible string which encodes almost as much polynomial-time CND complexity as the original string.
Supported in part by NSF grant CCR 92-53582, the Fulbright scholar program and the Dutch Foundation for Scientific Research (NWO). Some of this research was done while on leave at CWI in Amsterdam.
Supported in part by NSF grant CCR 92-53582.
Preview
Unable to display preview. Download preview PDF.
References
H. Buhrman and L. Fortnow. Resource-bounded kolmogorov complexity revisited. In Proceedings of the 14th Symposium on Theoretical Aspects of Computer Science, volume 1200 of Lecture Notes in Computer Science, pages 105–116. Springer, Berlin, 1997.
L. Fortnow and M. Kummer. Resource-bounded instance complexity. Theoretical Computer Science A, 161:123–140, 1996.
P. Orponen, K. Ko, U. Schöning, and O. Watanabe. Instance Complexity Journal of the ACM, 41(1):96–121, 1994.
M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, New York, second edition, 1997.
N. Nisan. Extracting randomness: How and why (a survey). In Proceedings of the 11th IEEE Conference on Computational Complexity, pages 44–58. IEEE, New York, 1996.
N. Nisan and D. Zuckerman. More deterministic simulation in logspace. In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 235–244. ACM, New York, 1993.
M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 330–335. ACM, New York, 1983.
A. Ta-Shma. On extracting randomness from weak random sources (extended abstract). In Proceedings of the 28th ACM Symposium on the Theory of Computing, pages 276–285. ACM, New York, 1996.
D. Zuckerman. Randomness-optimal sampling, extractors, and constructive leader election. In Proceedings of the 28th ACM Symposium on the Theory of Computing, pages 286–295. ACM, New York, 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Fortnow, L., Laplante, S. (1998). Nearly optimal language compression using extractors. In: Morvan, M., Meinel, C., Krob, D. (eds) STACS 98. STACS 1998. Lecture Notes in Computer Science, vol 1373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028551
Download citation
DOI: https://doi.org/10.1007/BFb0028551
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64230-5
Online ISBN: 978-3-540-69705-3
eBook Packages: Springer Book Archive