2 Search Results for "Gürpınar, Emirhan"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.84
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings

Authors: Andrei Romashchenko

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
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.
Cite as

Andrei Romashchenko. Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 84:1-84:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{romashchenko:LIPIcs.MFCS.2025.84,
  author =	{Romashchenko, Andrei},
  title =	{{Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{84:1--84:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.84},
  URN =		{urn:nbn:de:0030-drops-241914},
  doi =		{10.4230/LIPIcs.MFCS.2025.84},
  annote =	{Keywords: Kolmogorov complexity, algorithmic information theory, communication complexity, discrete geometry}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.44
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

Authors: Emirhan Gürpınar and Andrei Romashchenko

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key the size of which is much smaller than the mutual information between x and y. On the other hand, we provide examples of x, y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses spectral properties of appropriate graphs and the expander mixing lemma as well as various information theoretic techniques.
Cite as

Emirhan Gürpınar and Andrei Romashchenko. Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gurpinar_et_al:LIPIcs.MFCS.2020.44,
  author =	{G\"{u}rp{\i}nar, Emirhan and Romashchenko, Andrei},
  title =	{{Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.44},
  URN =		{urn:nbn:de:0030-drops-127102},
  doi =		{10.4230/LIPIcs.MFCS.2020.44},
  annote =	{Keywords: Kolmogorov complexity, mutual information, communication complexity, expander mixing lemma, finite geometry}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2020

  • Refine by Author
  • 2 Romashchenko, Andrei
  • 1 Gürpınar, Emirhan

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Information theory
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Theory of computation → Communication complexity
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Expander graphs and randomness extractors

  • Refine by Keyword
  • 2 Kolmogorov complexity
  • 2 communication complexity
  • 1 algorithmic information theory
  • 1 discrete geometry
  • 1 expander mixing lemma
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact