Sumários

Prefix-free Kolmogorov complexity

15 Dezembro 2015, 14:00 Paulo Alexandre Carreira Mateus

Motivation for prefix-free Kolmogorov complexity. Definition of prefix-free Kolmogorov complexity and its properties. Prefix-free Kolmogorov complexity and probability distributions. Three different approaches and the the Coding theorem. Application to Information theory.

Lecturer: Andre Souto.


Symmetry of Information

10 Dezembro 2015, 14:00 Paulo Alexandre Carreira Mateus

Considerations about mutual information a la Kolmogorov complexity. Proof that symmetry of information cannot hold up to constant terms. Statement and proof of symmetry of information with logarithmic terms. Digression to application on security.


Lecturer: Andre Souto.


There were no classes

3 Dezembro 2015, 14:00 Paulo Alexandre Carreira Mateus

There were no classes.


Incompressibility results

1 Dezembro 2015, 14:00 Paulo Alexandre Carreira Mateus

Revision of the topics of previous letter as a motivation for proving that if x=ywz is not compressible then neither of the 3 is compressible by log terms.
Proof of C(<x,y>) <= C(x) + C(y) +O(log min{C(x),c(y)} and its refinements.
Discussion on Language compression theorem.
Statement and initial consideration about symmetry of information. Its connection to information theory.


Lecturer: André Souto


The Kolmogorov-Solomonoff theorem of invariance

26 Novembro 2015, 14:00 Paulo Alexandre Carreira Mateus

The Kolmogorov-Solomonoff theorem of invariance. Examples of application.Upper bounds on Kolmogorov complexity. The incomputability theorem. Incompressibility theorem.


Lecturer: André Souto