### Article

## An additivity theorem for plain Kolmogorov complexity

PROCEEDINGS

2017 Fourth International Conference on Engineering and Telecommunication

We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by Li and Vit ́anyi in 1995 and corrected by Glier in 2003. The structural lemma allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha- y gin. Randomized Individual Communication Complexity. IEEE Con- ference on Computational Complexity 2008: 321-331] considered com- munication complexity of the following problem. Alice has a bi- nary string x and Bob a binary string y, both of length n, and they want to compute or approximate Kolmogorov complexity C(x|y) of x conditional to y. It is easy to show that deterministic communica- tion complexity of approximating C(x|y) with precision α is at least n − 2α − O(1). The above referenced paper asks what is random- ized communication complexity of this problem and shows that for r- round randomized protocols its communication complexity is at least Ω((n/α)1/r ). In this paper, for some positive ε, we show the lower bound 0.99n for (worst case) communication length of any random- ized protocol that with probability at least 0.01 approximates C(x|y) with precision εn for all input pairs.

Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string *x* is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of *x*. Further we will show how it can be used for list decoding from erasing and prove that Symmetry of Information fails for total conditional complexity.

In a collaborative system, the agents collaborate to achieve a common goal, but they are not willing to share some sensitive private information.

The question is how much damage can be done by a malicious participant sitting inside the system.

We assume that all the participants (including internal adversaries) have bounded memory – at any moment, they can store only a fixed number of messages of a fixed size. The Dolev–Yao adversaries can compose, decompose, eavesdrop, and intercept messages, and create fresh values (nonces), but within their bounded memory.

We prove that the secrecy problem is PSPACE-complete in the bounded memory model where all actions are balanced and a potentially infinite number of the nonce updates is allowed.

We also show that the well-known security protocol anomalies (starting from the Lowe attack to the Needham–Schroeder protocol) can be rephrased within the bounded memory paradigm with the explicit memory bounds.

Bacteria has been proposed in recent years as one approach to achieve molecular communication. Bacterial cells can harbour DNA encoded information and can deliver this information from one nanomachine to another by swimming (motility). One aspect of bacterial communication that could further enhance the performance of information delivery in bacterial nanonetworks is *conjugation*. Conjugation involves forming a physical connection between the bacteria in order to transfer DNA molecules (i.e., plasmids or chromosomes). However, the fragile physical connection between the bacteria is prone to breakage, in particular under mechanical stress. In this paper, a simple *Forward and Reverse* coding process is proposed to enhance the performance of information delivery in bacterial nanonetworks. The coding process involves segmenting messages into blocks and integrating this into the bacterial chromosome. Simulation work have been conducted to validate the efficiency of the coding process, where the results have shown positive performance compared to approaches that do not utilize coding or pure conjugation.