Anúncios

Final grades

8 fevereiro 2016, 13:32 • Paulo Alexandre Carreira Mateus

The final grades are available here.

Grades for 1st, 2nd and 4th HW

25 janeiro 2016, 16:04 • Paulo Alexandre Carreira Mateus

Dear Students
Please find here the grades for the 1st, 2nd and 4th Homework. The grades take into account quality, originality and clarity of the proofs.

Schedule your presentation using this Doodle link.

Students should attend, as possible, the other talks. The presentations are at room P9

Best
Paulo Mateus 

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 


Presentation topics in information theory

18 dezembro 2015, 15:15 • Mário Alexandre Teles de Figueiredo

A. Montanari, R. Urbanke, "Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View", http://arxiv.org/abs/0704.2857 

 

A. Lesne, "Shannon entropy: a rigorous mathematical notion at the crossroads between probability, information theory, dynamical systems and statistical physics", available at http://www.lptmc.jussieu.fr/user/lesne/MSCS-entropy.pdf.

 

C. Adami, "Information theory in molecular biology", available at http://adamilab.msu.edu/wp-content/uploads/Reprints/2004/Adami2004.pdf 

 

F. Fabris, "Shannon Information Theory and Molecular Biology", available at http://www.dmi.units.it/~fabris/Inf_Th_Mol_Bio.pdf



Information Theory Problems

18 dezembro 2015, 15:11 • Mário Alexandre Teles de Figueiredo

Please solve the following problems from the 2006 edition of the book "Elements of Information Theory" (Cover and Thomas): 2.7, 2.17, 2.48, 3.10, 5.25, and 5.32.