Topological arguments in Kolmogorov complexity
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Mustapha Amrani.
Semantics and Syntax: A Legacy of Alan Turing
We show how topological arguments (simple facts about nonhomotopic 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(xy) and C(yx) are equal to n+O(1).
This talk is part of the Isaac Newton Institute Seminar Series series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
