Ξ welcome to cryptostorm's member forums ~ you don't have to be a cryptostorm member to post here Ξ
Ξ any OpenVPN configs found on the forum are likely outdated. For the latest, visit here or GitHub Ξ
Ξ If you're looking for tutorials/guides, check out the new https://cryptostorm.is/#section6 Ξ

Topological arguments for Kolmogorov complexity (pdf)

Freewheeling spot to chew the fat on anything cryptostorm-related that doesn't fit elsewhere (i.e. support, howto, &c.). Criticism & praise & brainstorming & requests for explanation... this is where it goes when it's hot & ready for action! :-)
User avatar

Topic Author
Pattern_Juggled
Posts: 1492
Joined: Sun Dec 16, 2012 6:34 am
Contact:

Topological arguments for Kolmogorov complexity (pdf)

Postby Pattern_Juggled » Thu Oct 31, 2013 11:47 am

Topological arguments for Kolmogorov complexity

Alexander Shen
alexander.shen@lirmm.fr

Andrei Romashchenko
andrei.romashchenko@lirmm.fr

We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connected. It proves to be enough to construct strings with some nontrivial algorithmic properties.

1206.4927.pdf
(127.66 KiB) Downloaded 376 times


Introduction

In this paper we show that a very simple and intuitive topological technique can be surprisingly effective in algorithmic information theory. We present several examples of “topological” proofs of existence of strings with some nontrivial algorithmic properties. We focus on technical aspects of the arguments, assuming that the reader is familiar with basic notions of algorithmic information theory such as Kolmogorov complexity and the mutual information (see the classic textbook [1]).

Let us start with an example. Consider a string x that has complexity n (we consider plain complexity C(x), but this does not matter for now). We want to find a string y such that C(x|y) ≈ n/2. This can be done as follows: consider the shortest description p of x; it has length n; let y be the first half of this description. Then it is easy to check that C(x|y) = n/2 + O(log n). However, if we want C(x|y) to be close to n/2 with (maximal possible) precision O(1), one needs a different argument. Let us start with y = x (when C(x|y) ≈ 0) and delete bits (say, at the end) one by one until we get y = Λ (the empty string) when C(x|y) ≈ n). When the last bit of y is deleted, the conditional complexity C(x|y) changes by at most O(1), so it cannot cross the threshold n/2 without visiting O(1)-neighborhood of n/2. Topological arguments of this type can be used in two (and more) dimensions, though they become a bit less trivial. We provide several examples of this type in the following sections.
...just a scatterbrained network topologist & crypto systems architect……… ҉҉҉

    ✨ ✨ ✨
pj@ðëëþ.bekeybase pgpmit pgpðørkßöt-on-consolegit 'er github
bitmessage:
BM-NBBqTcefbdgjCyQpAKFGKw9udBZzDr7f

Return to “general chat, suggestions, industry news”

Who is online

Users browsing this forum: No registered users and 29 guests

cron

Login