Sumários

Computational depth and application of resource bounded Kolmogorovo complexity to security

4 dezembro 2014, 17:30 • Paulo Alexandre Carreira Mateus

Time bounded and space bounded Kolmogorov complexity classes.
Proof that size of description is an independent parameter than time and space.
Computational depth a measure of information usefulness.
Examples of deep objects.
Proof that the number of deep strings increases exponentially with size.
Computational depth of average case complexity.
Applications of resourced-bound Kolmogorov complexity to cryptography. The case of one-way functions.

Resource bounded Kolmoogorov complexity

2 dezembro 2014, 17:30 • Paulo Alexandre Carreira Mateus

Applications of coding theorem.
Proof that for recursive probability distributions, the executed value of the Kolmogorov complexity is, up to a constant that depends only on the distribution, entropy of the distribution.
Proof that worst case is of same order of average case complexity when the inputs are drawn according to m.
Resource bounded Kolmogorov complexity. Definition and the resource bounded version of Kolmogorov-Solomonoff theorem.
Resource bounded distinguishing complexity. Definition and relations to resource bounded Kolmogorov complexity.

Lecture given by André Souto

Prefix free Kolmogorov complexity and coding theorem

27 novembro 2014, 17:30 • Paulo Alexandre Carreira Mateus

Improved versions and respective bounds for Symmetry of information.

Applications of symmetry of information and the incompressibility theorem.

Limitations of plain Kolmogorov complexity as motivation for prefix-free version.
Notions of prefix free Turing machines and the existence of universal element.
Subadditivity of prefix free Kolmogorov complexity.
The use of Kolmogorov complexity to define semiprobability measures that are lower semi computable. Universal distribution, a priori distribution and the distribution R(x)=2^{-K(x)}.
Kraft inequality.
Coding theorem to establish that the three distributions above are related up to a multiplicative factor.
 
Lecture given by André Souto

Symmetry theorem

25 novembro 2014, 17:30 • Paulo Alexandre Carreira Mateus

Proof that C(<x,y>) <= C(x) + C(y) +O(log min C(x), C(y)) and why the log term cannot be avoided.

Language compression Theorem.

Kolmogorov complexity proof that BPP is contained in P/Poly.

Symmetry of information for Algorithm Information theory. Theorem and proof.


Lecture given by André Souto

Incompressible theorem

20 novembro 2014, 17:30 • Paulo Alexandre Carreira Mateus

Proof that C is always finite.

Derivation of upper bounds for Kolmogorov complexity of objects.

Examples of application.

Notion of c-incompressible/c-random object.

Incompressibility theorem. Proof and implications.

Proof that C is not computable.

Examples of application.



Lecture given by André Souto