License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.95
URN: urn:nbn:de:0030-drops-90998
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9099/
Go to the corresponding LIPIcs Volume Portal

Romashchenko, Andrei ; Zimand, Marius

An Operational Characterization of Mutual Information in Algorithmic Information Theory

pdf-format:
LIPIcs-ICALP-2018-95.pdf (0.4 MB)

Abstract

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair, can establish via a probabilistic protocol with interaction on a public channel. For l > 2, the longest shared secret that can be established from a tuple of strings (x_1, . . . , x_l) by l parties, each one having one component of the tuple and the complexity profile of the tuple, is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length, for protocols with public randomness. We also show that if the communication complexity drops below the established threshold then only very short secret keys can be obtained.

BibTeX - Entry

@InProceedings{romashchenko_et_al:LIPIcs:2018:9099,
  author =	{Andrei Romashchenko and Marius Zimand},
  title =	{{An Operational Characterization of Mutual Information in Algorithmic Information Theory}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{95:1--95:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9099},
  URN =		{urn:nbn:de:0030-drops-90998},
  doi =		{10.4230/LIPIcs.ICALP.2018.95},
  annote =	{Keywords: Kolmogorov complexity, mutual information, communication complexity, secret key agreement}
}

Keywords: Kolmogorov complexity, mutual information, communication complexity, secret key agreement
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI