Evaluation results (provisory)

19 Janeiro 2015, 09:53 Amilcar Sernadas

Evaluation results (provisory)

Any issue that you may have should be taken to the Lecturer of the Module before Thursday January 22, 8 AM.

The final results will be registered on Friday.

Presentation Schedule II

19 Dezembro 2014, 15:12 Paulo Alexandre Carreira Mateus

The schedule for the presentations is the following:

Room 4.35 Department of Mathematics

  • January 5th
    • 14:00 - J. Rodrigues - Adabatic quantum computing
    • 15:00 - S. Chakraborty - Strengths and weaknesses of quantum computing
  • January 6th
    • 14:00 - L. Novo - Shor's algorithm [Postponed to 14th]
    • 15:00 - C. Vlachou - Algorithmic Complexity and entanglement [Postponed to 14th]
  • January 7th
    • 14:00 - M. Pezzutto - Kolmogorov complexity and information theory
  • January  12th
    • 14:00 - F. Casal - Algebrazation in complexity theory  
    • 15:00 - G. Ramos - Derandomizing from random strings
  • January  13th
    • 14:00 - B. Richter - Information theory in molecular biology
  • January 14th
    • 14:00 - L. Novo - Shor's algorithm
    • 15:00 - C. Vlachou - Algorithmic Complexity and entanglement

The presentations take 45 minutes plus 15 minutes of discussion.

Presentation schedule

2 Dezembro 2014, 15:46 Paulo Alexandre Carreira Mateus

The presentations of research topics are postponed to the period of January 5-16, 2015. The students will be contacted by mail next week to schedule their presentations in the mentioned period. The schedule with all the presentations will be made available in the course webpage. 

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

Presentation topics in information theory

19 Novembro 2014, 15:52 Mário Alexandre Teles de Figueiredo


A. Montanari, R. Urbanke, "Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View", 


A. Lesne, "Shannon entropy: a rigorous mathematical notion at the crossroads between probability, information theory, dynamical systems and statistical physics", available at


C. Adami, "Information theory in molecular biology", available at 


F. Fabris, "Shannon Information Theory and Molecular Biology", available at