Explore the vast range of titles available.

Van Lambalgen’s theorem states that a pair ( α , β ) of bit sequences is Martin-Löf random if and only if α is Martin-Löf random and β is Martin-Löf random relative to α . In [Information and Computation 209.2 (2011): 183-197, Theorem 3.3], Hayato Takahashi generalized van Lambalgen’s theorem for computable measures P on a product of two Cantor spaces; he showed that the equivalence holds for each β for which the conditional probability P (⋅| β ) is computable. He asked whether this computability condition is necessary. We give a positive answer by providing a computable measure for which van Lambalgen’s theorem fails. We also present a simple construction of a computable measure for which conditional measure is not computable. Such measures were first constructed by Ackerman et al. ([ 1 ]).

In (Bauwens and Shen, J. Symb. Log. 79 (2), 620–632, 2013 ) a short proof is given that some strings have maximal plain Kolmogorov complexity but not maximal prefix-free complexity. We argue that the proof technique is useful to simplify existing proofs and to solve open questions. We present a short proof of a result due to Robert Solovay that relates plain and prefix complexity: K ( x ) = C ( x ) + C C ( x ) + O ( CCC ( x ) ) C ( x ) = K ( x ) − K K ( x ) + O ( KKK ( x ) ) , (here CC ( x ) denotes C ( C ( x )), etc.). We show that there exist ω such that liminf C ( ω 1 … ω n ) − C ( n ) is infinite and liminf K ( ω 1 … ω n ) − K ( n ) is finite, i.e. the infinitely often C -trivial reals are not the same as the infinitely often K -trivial reals, answering Question 1 in Barmpalias (Bull. Symb. Log. 19 (3), 2013 ). We answer a question from Bienvenu (Laurent Bienvenu, personal communication 2011): some 2-random sequence has a family of initial segments with bounded plain deficiency (i.e. | x |− C ( x ) is bounded) and unbounded prefix deficiency (i.e. | x |+ K (| x |)− K ( x ) is unbounded). Finally, we show that there exists no monotone relation between probability and expectation bounded randomness deficiency, answering Question 1 in Bienvenu et al. (Proceedings of the Steklov Institute of Mathematics, 274 (1), 34–89, 2011 ).

The definition of conditional probability in the case of continuous distributions (for almost all conditions) was an important step in the development of mathematical theory of probabilities. Can we define this notion in algorithmic probability theory for individual random conditions? Can we define randomness with respect to the conditional probability distributions? Can van Lambalgen’s theorem (relating randomness of a pair and its elements) be generalized to conditional probabilities? We discuss the developments in this direction. We present almost no new results trying to put known results into perspective and explain their proofs in a more intuitive way. We assume that the reader is familiar with basic notions of measure theory and algorithmic randomness (see, e.g., Shen et al. ??2013 or Shen ??2015 for a short introduction).

We prove the formula C ( a , b )= K ( a | C ( a , b ))+ C ( b | a , C ( a , b ))+ O (1) that expresses the plain complexity of a pair in terms of prefix-free and plain conditional complexities of its components.

Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x. i.e.. C(C(x)|x) ≥ log n — log⁽²⁾ n — O(1). (Here log⁽²⁾ i= log log i.) Following Elena Kalinina (Kalinina 2011). we provide a simple game-based proof of this result: modifying her argument, we get a better (and tight) bound log n — O(1). We also show the same bound for prefix-free complexity. Robert Solovay showed (Solovay 1975) that infinitely many strings x have maximal plain complexity but not maximal prefix complexity (among the strings of the same length): for some c there exist infinitely many x such that |x| — C(x) ≤ c and |x| + K(|x|) — K(x) ≥ log ⁽²⁾ |x| — c log ⁽³⁾ |x|. In fact, the results of Solovay and Gacs are closely related. Using the result above, we provide a short roof for Solovay's result. We also generalize it by showing that for some c and for all n there are strings x of length n with n — C(x) ≤ c and n + K(n) — K(x) ≥ K(K(n)|n) - 3 K(K(K(n)|n)|n) — c. We also prove a close upper bound K(K(n)|n) + O(1). Finally, we provide a direct game proof for Joseph Miller's generalization (Miller 2006) of the same Solovay's theorem: if a co-enumerable set (a set with co-enumerable complement) contains for every length a string of this length, then it contains infinitely many strings x such that |x| + K(|x|) — K(x) ≥ log⁽²⁾ |x| — O(log⁽³⁾ |x|) .

Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program that is shortest within some precision. We show that the Busy Beaver function of the sophistication of a string exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the Busy Beaver function of sophistication with logarithmically bigger precision. We also show that sophistication is unstable in its precision: constant variations can change its value by a linear term in the length of the string.

We study connections between expansion in bipartite graphs and efficient online matching modeled via several games. In the basic game, an opponent switches {\\em on} and {\\em off} nodes on the left side and, at any moment, at most \\(K\\) nodes may be on. Each time a node is switched on, it must be irrevocably matched with one of its neighbors. A bipartite graph has \\(e\\)-expansion up to \\(K\\) if every set \\(S\\) of at most \\(K\\) left nodes has at least \\(e\\#S\\) neighbors. If all left nodes have degree \\(D\\) and \\(e\\) is close to \\(D\\), then the graph is a lossless expander. We show that lossless expanders allow for a polynomial time strategy in the above game, and, furthermore, with a slight modification, they allow a strategy running in time \\(O(D \\log N)\\), where \\(N\\) is the number of left nodes. Using this game and a few related variants, we derive applications in data structures and switching networks. Namely, (a) 1-query bitprobe storage schemes for dynamic sets (previous schemes work only for static sets),(b) explicit space- and time-efficient storage schemes for static and dynamic sets with non-adaptive access to memory (the first fully dynamic dictionary with non-adaptive probing using almost optimal space), and (c) non-explicit constant depth non-blocking \\(N\\)-connectors with poly\\((\\log N)\\) time path finding algorithms whose size is optimal within a factor of \\(O(\\log N)\\) (previous connectors are double-exponentially slower).

We consider the notion of information distance between two objects \\(x\\) and \\(y\\) introduced by Bennett, Gács, Li, Vitányi, and Zurek in 1998 as the minimal length of a program that computes \\(x\\) from \\(y\\) as well as computing \\(y\\) from \\(x\\). In this paper, it was proven that the distance is equal to \\(\\max (K(x|y),K(y|x))\\) up to additive logarithmic terms, and it was conjectured that this could not be improved to \\(O(1)\\) precision. We revisit subtle issues in the definition and prove this conjecture. We show that if the distance is at least logarithmic in the length, then this equality does hold with \\(O(1)\\) precision for strings of equal length. Thus for such strings, both the triangle inequality and the characterization hold with optimal precision. Finally, we extend the result to sets \\(S\\) of bounded size. We show that for each constant~\\(s\\), the shortest program that prints an \\(s\\)-element set \\(S \\subseteq \\{0,1\\}^n\\) given any of its elements, has length at most \\(\\max_{w \\in S} K(S|w) + O(1)\\), provided this maximum is at least logarithmic in~\\(n\\).

We show that there exists a bitsequence that is not computably random for which its odd bits are computably random and its even bits are computably random relative to the odd bits. This implies that the uniform variant of van Lambalgen's theorem fails for computable randomness. (The other direction of van Lambalgen's theorem is known to hold in this case, and known to fail for the non-uniform variant.)

We put forth new models for universal channel coding. Unlike standard codes which are designed for a specific type of channel, our most general universal code makes communication resilient on every channel, provided the noise level is below the tolerated bound, where the noise level t of a channel is the logarithm of its ambiguity (the maximum number of strings that can be distorted into a given one). The other more restricted universal codes still work for large classes of natural channels. In a universal code, encoding is channel-independent, but the decoding function knows the type of channel. We allow the encoding and the decoding functions to share randomness, which is unavailable to the channel. There are two scenarios for the type of attack that a channel can perform. In the oblivious scenario, codewords belong to an additive group and the channel distorts a codeword by adding a vector from a fixed set. The selection is based on the message and the encoding function, but not on the codeword. In the Hamming scenario, the channel knows the codeword and is fully adversarial. For a universal code, there are two parameters of interest: the rate, which is the ratio between the message length k and the codeword length n, and the number of shared random bits. We show the existence in both scenarios of universal codes with rate 1-t/n - o(1), which is optimal modulo the o(1) term. The number of shared random bits is O(log n) in the oblivious scenario, and O(n) in the Hamming scenario, which, for typical values of the noise level, we show to be optimal, modulo the constant hidden in the O() notation. In both scenarios, the universal encoding is done in time polynomial in n, but the channel-dependent decoding procedures are in general not efficient. For some weaker classes of channels we construct universal codes with polynomial-time encoding and decoding.