Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914117100503040 |
|---|---|
| author | Romashchenko, Andrei |
| author_facet | Romashchenko, Andrei |
| contents | We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings $(a, b, c)$, there exists a string $z$ such that each conditional Kolmogorov complexity $C(a|z), C(b|z), C(c|z)$ is approximately half of the corresponding unconditional Kolmogorov complexity. We give a negative answer to this question by constructing a triple $(a, b, c)$ for which no such string $z$ exists. Moreover, we construct a fully explicit example of such a tuple. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on bounds for point-line incidences over prime fields. As an application, we show that this impossibility yields lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in information-theoretic behavior between fields with and without proper subfields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14408 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings Romashchenko, Andrei Information Theory Discrete Mathematics We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings $(a, b, c)$, there exists a string $z$ such that each conditional Kolmogorov complexity $C(a|z), C(b|z), C(c|z)$ is approximately half of the corresponding unconditional Kolmogorov complexity. We give a negative answer to this question by constructing a triple $(a, b, c)$ for which no such string $z$ exists. Moreover, we construct a fully explicit example of such a tuple. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on bounds for point-line incidences over prime fields. As an application, we show that this impossibility yields lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in information-theoretic behavior between fields with and without proper subfields. |
| title | Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings |
| topic | Information Theory Discrete Mathematics |
| url | https://arxiv.org/abs/2504.14408 |