# SAS

## Seminar

### Topological arguments in Kolmogorov complexity

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

## Comments

Start the discussion!