2026-07-23T16:56:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24191 2025-11-12T13:34:24Z ddc:004 open_access

Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings Romashchenko, Andrei Kolmogorov complexity algorithmic information theory communication complexity discrete geometry 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 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 for point-line incidences over prime fields, obtained using tools from additive combinatorics and algebraic methods, notably results by Bourgain-Katz-Tao and Stevens-De Zeeuw. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei Romashchenko 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.84 urn:nbn:de:0030-drops-241914 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.84 eng https://creativecommons.org/licenses/by/4.0/legalcode