skip to content
 

Topological arguments in Kolmogorov complexity

Presented by: 
A Shen Université de Montpellier 2
Date: 
Monday 2nd July 2012 - 14:00 to 15:00
Venue: 
INI Seminar Room 1
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

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.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons