<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of lirmm-05041918</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-22T14:45:15+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings</title>
            <author role="aut">
              <persName>
                <forename type="first">Andrei</forename>
                <surname>Romashchenko</surname>
              </persName>
              <email type="md5">98c085f266726e07926c57354c375025</email>
              <email type="domain">ens-lyon.fr</email>
              <ptr type="url" target="http://www.lirmm.fr/~romashchen"/>
              <idno type="idhal" notation="string">andrei-romashchenko</idno>
              <idno type="idhal" notation="numeric">81</idno>
              <idno type="halauthorid" notation="string">17831-81</idno>
              <idno type="RESEARCHERID">http://www.researcherid.com/rid/H-7456-2012</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-7723-7880</idno>
              <idno type="IDREF">https://www.idref.fr/165481277</idno>
              <idno type="RESEARCHERID">http://www.researcherid.com/rid/http://www.researcherid.com/rid/H-7456-2012</idno>
              <idno type="ARXIV">https://arxiv.org/a/romashchenko_a_1</idno>
              <idno type="GOOGLE SCHOLAR">https://scholar.google.fr/citations?user=WmvoaNcAAAAJ</idno>
              <affiliation ref="#struct-1100637"/>
              <affiliation ref="#struct-441569"/>
              <affiliation ref="#struct-1100620"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Andrei</forename>
                <surname>Romashchenko</surname>
              </persName>
              <email type="md5">c143839ff1ebb1a2528efa601d5185d0</email>
              <email type="domain">lirmm.fr</email>
            </editor>
            <funder ref="#projanr-57027"/>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2025-04-22 09:34:57</date>
              <date type="whenModified">2026-02-12 03:25:58</date>
              <date type="whenReleased">2025-04-23 13:12:44</date>
              <date type="whenProduced">2026-01</date>
              <ref type="externalLink" target="http://arxiv.org/pdf/2504.14408"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="176108">
                <persName>
                  <forename>Andrei</forename>
                  <surname>Romashchenko</surname>
                </persName>
                <email type="md5">c143839ff1ebb1a2528efa601d5185d0</email>
                <email type="domain">lirmm.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-05041918</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-05041918</idno>
            <idno type="halBibtex">romashchenko:lirmm-05041918</idno>
            <idno type="halRefHtml">&lt;i&gt;Information and Computation&lt;/i&gt;, 2026, 308, pp.105396. &lt;a target="_blank" href="https://dx.doi.org/10.1016/j.ic.2025.105396"&gt;&amp;#x27E8;10.1016/j.ic.2025.105396&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Information and Computation, 2026, 308, pp.105396. &amp;#x27E8;10.1016/j.ic.2025.105396&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="UNIV-MONTP3">Université de Montpellier Paul-Valéry</idno>
            <idno type="stamp" n="UNIV-PERP">Université Perpignan Via Domitia</idno>
            <idno type="stamp" n="ECO" corresp="LIRMM">Exact Computing</idno>
            <idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno>
            <idno type="stamp" n="TDS-MACS">Réseau de recherche en Théorie des Systèmes Distribués, Modélisation, Analyse et Contrôle des Systèmes</idno>
            <idno type="stamp" n="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="ANR">ANR</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
            <idno type="stamp" n="UM-EPE" corresp="UNIV-MONTPELLIER">Université de Montpellier - EPE</idno>
          </seriesStmt>
          <notesStmt>
            <note type="commentary">A preliminary version of the paper was published in proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), https://mfcs2025.mimuw.edu.pl/ ; DOI:10.4230/LIPIcs.MFCS.2025.84,  https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.84</note>
            <note type="audience" n="2">International</note>
            <note type="invited" n="0">No</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Andrei</forename>
                    <surname>Romashchenko</surname>
                  </persName>
                  <email type="md5">98c085f266726e07926c57354c375025</email>
                  <email type="domain">ens-lyon.fr</email>
                  <ptr type="url" target="http://www.lirmm.fr/~romashchen"/>
                  <idno type="idhal" notation="string">andrei-romashchenko</idno>
                  <idno type="idhal" notation="numeric">81</idno>
                  <idno type="halauthorid" notation="string">17831-81</idno>
                  <idno type="RESEARCHERID">http://www.researcherid.com/rid/H-7456-2012</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-7723-7880</idno>
                  <idno type="IDREF">https://www.idref.fr/165481277</idno>
                  <idno type="RESEARCHERID">http://www.researcherid.com/rid/http://www.researcherid.com/rid/H-7456-2012</idno>
                  <idno type="ARXIV">https://arxiv.org/a/romashchenko_a_1</idno>
                  <idno type="GOOGLE SCHOLAR">https://scholar.google.fr/citations?user=WmvoaNcAAAAJ</idno>
                  <affiliation ref="#struct-1100637"/>
                  <affiliation ref="#struct-441569"/>
                  <affiliation ref="#struct-1100620"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">14180</idno>
                <idno type="issn">0890-5401</idno>
                <idno type="eissn">1090-2651</idno>
                <title level="j">Information and Computation</title>
                <imprint>
                  <publisher>Elsevier</publisher>
                  <biblScope unit="volume">308</biblScope>
                  <biblScope unit="pp">105396</biblScope>
                  <date type="datePub">2026-01</date>
                </imprint>
              </monogr>
              <idno type="arxiv">2504.14408</idno>
              <idno type="doi">10.1016/j.ic.2025.105396</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">communication complexity</term>
                <term xml:lang="en">algorithmic information theory</term>
                <term xml:lang="en">Kolmogorov complexity</term>
                <term xml:lang="en">Common information</term>
                <term xml:lang="en">discrete geometry</term>
              </keywords>
              <classCode scheme="halDomain" n="math.math-it">Mathematics [math]/Information Theory [math.IT]</classCode>
              <classCode scheme="halDomain" n="info.info-cc">Computer Science [cs]/Computational Complexity [cs.CC]</classCode>
              <classCode scheme="halDomain" n="info.info-dm">Computer Science [cs]/Discrete Mathematics [cs.DM]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>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.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-1100637" status="VALID">
          <orgName>Exact Computing</orgName>
          <orgName type="acronym">LIRMM | ECO</orgName>
          <date type="start">2022-01-01</date>
          <desc>
            <address>
              <addrLine>LIRMM, 161 rue Ada, 34000 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr/equipes/eco</ref>
          </desc>
          <listRelation>
            <relation active="#struct-1100620" type="direct"/>
            <relation active="#struct-101475" type="indirect"/>
            <relation active="#struct-300009" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
            <relation name="UMR5506" active="#struct-1100589" type="indirect"/>
            <relation active="#struct-1219853" type="indirect"/>
          </listRelation>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-1100620" status="VALID">
          <idno type="IdRef">139590827</idno>
          <idno type="ISNI">0000000405990488</idno>
          <idno type="RNSR">199111950H</idno>
          <idno type="ROR">https://ror.org/013yean28</idno>
          <orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
          <orgName type="acronym">LIRMM</orgName>
          <date type="start">2022-01-01</date>
          <desc>
            <address>
              <addrLine>161 rue Ada - 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr</ref>
          </desc>
          <listRelation>
            <relation active="#struct-101475" type="direct"/>
            <relation active="#struct-300009" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
            <relation name="UMR5506" active="#struct-1100589" type="direct"/>
            <relation active="#struct-1219853" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-101475" status="VALID">
          <idno type="ROR">https://ror.org/03am2jy38</idno>
          <orgName>Université de Perpignan Via Domitia</orgName>
          <orgName type="acronym">UPVD</orgName>
          <desc>
            <address>
              <addrLine>52 avenue Paul Alduy - 66860 Perpignan Cedex 9</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.univ-perp.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-300009" status="VALID">
          <idno type="ROR">https://ror.org/02kvxyf05</idno>
          <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
          <orgName type="acronym">Inria</orgName>
          <desc>
            <address>
              <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.inria.fr/en/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-1100589" status="VALID">
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="start">2022-01-01</date>
          <desc>
            <address>
              <addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.umontpellier.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-1219853" status="VALID">
          <idno type="IdRef">282217916</idno>
          <orgName>Université de Montpellier Paul-Valéry</orgName>
          <orgName type="acronym">UMPV</orgName>
          <date type="start">2025-01-01</date>
          <desc>
            <address>
              <addrLine>Université de Montpellier Paul-Valéry Route de Mende 34199 Montpellier Cedex 5</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.univ-montp3.fr/fr</ref>
          </desc>
        </org>
      </listOrg>
      <listOrg type="projects">
        <org type="anrProject" xml:id="projanr-57027" status="VALID">
          <idno type="anr">ANR-21-CE48-0023</idno>
          <orgName>FLITTLA</orgName>
          <desc>Lois fondamentales de la théorie de l'information à travers le prisme des applications</desc>
          <date type="start">2021</date>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>