Article Dans Une Revue Information and Computation Année : 2026

Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings

Résumé

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 of the values of conditional Kolmogorov complexity C(a|z), C(b|z), C(c|z) is approximately half of the corresponding unconditional Kolmogorov complexity. We provide a negative answer to this question by constructing a triple (a, b, c) for which no such string z exists. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on recent bounds on point-line incidences over prime fields. As an application, we show that this impossibility implies 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 the information-theoretic behavior of projective planes over fields with and without proper subfields.

Dates et versions

lirmm-05041918 , version 1 (22-04-2025)

Identifiants

Citer

Andrei Romashchenko. Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings. Information and Computation, 2026, 308, pp.105396. ⟨10.1016/j.ic.2025.105396⟩. ⟨lirmm-05041918⟩
188 Consultations
0 Téléchargements

Altmetric

Partager

  • More