Presentation topics in computability and complexity and Kolmogorov Compleixty

23 dezembro 2015, 11:55 • Paulo Alexandre Carreira Mateus

[Shor97] P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (5): 1484–1509, 1997.

[AR06] A. Ambainis and O. Regev. An elementary proof of the quantum adiabatic theorem. arXiv:quant-ph/0411152.

[CGW13] A. Childs, D. Gosset and Z. Webb. Universal Computation by Multiparticle Quantum Walk. Science 339(6121):791-794, 2013.

[AW09] S. Aaronson and A. Wigderson; Algebrization. A new barrier in Complexity Theory. ACM Trans. Comput. Theory 1: 2-54, 2009.

[GMW91] O. Goldreich, S. Micali and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of ACM 38(3):690-728, 1991.

[CGW15] T. Cubitt, D. Perez-Garcia and M. Wolf. Undecidability of the spectral gap. Nature 528 (7581): 207-211,2015.



[AFPS12] L. Antunes, L. Fortnow, A. Pinto, A.Souto: low depth witnesses are easy to find, Computationla Complexity, 21:479-497, 2012

[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, Journal of Computer and System Sciences, 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.

[FK] L. Fortnow, M. Kummer: On resource-bounded instance complxity, Theoretical Computer Science, 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. Longpre, S. Mocas: Symmetry of Information and One-Way Functions. Inf. Process. Lett. 46(2): 95-100 (1993)

[MB05] C. Mora, H. Briegel, Algorithmic Complexity and Entanglement of Quantum States, Physical Review Letters 95:200503, 2005

[Vit01] Quantum Kolmogorov Complexity Based on Classical Descriptions, Trans. of Info. Theory, 47(6):2464, 2001