The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

SAS

Seminar

Topological arguments in Kolmogorov complexity

Shen, A (Université de Montpellier 2)
Monday 02 July 2012, 14:00-15:00

Seminar Room 1, Newton Institute

Abstract

We show how topological arguments (simple facts about non-homotopic mappings) can be used to prove result about Kolmogorov complexity. In particular, we show that for every string x of complexity at least n +c log n one can find a string y such that both conditional complexities C(x|y) and C(y|x) are equal to n+O(1).

See also: http://arxiv.org/abs/1206.4927

Presentation

[pdf ]

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧