Presentation topics in Kolmogorov Complexity

26 Novembro 2014, 11:27 Paulo Alexandre Carreira Mateus

[ALPS07] L. Antunes, S. Laplante, A. Pinto, L. Salvador: Cryptographic security of individual instances, Proceedings of International Conference on Information Theoretic Security 2007, pp. 195-210. 

[B88] C. Bennett: Logical Depth and Physical Complexity. In the book The Universal Turing Machine: a Half-Century Survey. Oxford University Press. pp. 227–257. 1988 

[BDL01] A. Berthiaume, W. van Dam, S. Laplante, Quantum Kolmogorov Complexity, Complexity 2000, 240-249. JCSS, Special Issue on Complexity 2000, 63(2):201-221, 2001. 

[BFKL10] H. Buhrman, L. Fortnow, M. Koucky, and B. Loff: Derandomizing from random strings. In Proceedings of the 25th IEEE Conference on Computational Complexity, pages 58-63. IEEE, 2010. 

[CV05] R. Cilibrasi, P. Vitanyi: Clustering by compression, IEEE Trans. Information Theory, 51(4): 1523- 1545 2005. 

[FK96] L. Fortnow and M. Kummer. On resource-bounded instance complexity. Theoretical Computer Science A, 161:123-140, (1996). 

[Gac01] P. Gacs: Quantum algorithmic entropy. Journal of Physics A: Mathematical and General, 34(35):6859, 2001 

[GV03] P. Grunwald, P.M.B. Vitanyi: Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers. J. Logic, Language, and Information, 12(4):497--529, 2003. 

[LM93] L. Longpré, S. Mocas: Symmetry of Information and One-Way Functions. Inf. Process. Lett. 46(2): 95-100 (1993) 

[MB05] C. Mora and H. Briegel: Algorithmic Complexity and Entanglement of Quantum States. Phys. Rev. Lett. 95, 200503, (2005)

[Vit01] P. Vitanyi, Quantum Kolmogorov complexity using classical descriptions, IEEE Trans. Inform. Theory, 47(6): 2464-2479, (2001)

The papers are available here.

André Souto