Search Results

Documents authored by Zimand, Marius

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.92
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

Authors: Zhenjian Lu, Igor C. Oliveira, and Marius Zimand

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The classical coding theorem in Kolmogorov complexity states that if an n-bit string x is sampled with probability δ by an algorithm with prefix-free domain then 𝖪(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [Zhenjian Lu and Igor C. Oliveira, 2021] established an unconditional time-bounded version of this result, by showing that if x can be efficiently sampled with probability δ then rKt(x) = O(log(1/δ)) + O(log n), where rKt denotes the randomized analogue of Levin’s Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a O(log(1/δ)) bound instead of the information-theoretic optimal log(1/δ). Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows. • Efficient coding theorem for rKt with a factor of 2. Addressing a question from [Zhenjian Lu and Igor C. Oliveira, 2021], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) ⋅ log(1/δ) + O(log n). As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given x, the code of the sampler, and δ, it outputs, with probability ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound. • Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 - o(1)) ⋅ log(1/δ) + poly(log n). Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. • Optimal coding theorem for pK^t and unconditional Antunes-Fortnow. We consider pK^t complexity [Halley Goldberg et al., 2022], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK^t, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [Luis Filipe Coelho Antunes and Lance Fortnow, 2009] which characterizes the worst-case running times of languages that are in average polynomial-time over all 𝖯-samplable distributions.
Cite as

Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 92:1-92:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ICALP.2022.92,
  author =	{Lu, Zhenjian and Oliveira, Igor C. and Zimand, Marius},
  title =	{{Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{92:1--92:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.92},
  URN =		{urn:nbn:de:0030-drops-164331},
  doi =		{10.4230/LIPIcs.ICALP.2022.92},
  annote =	{Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.21
Secret Key Agreement from Correlated Data, with No Prior Information

Authors: Marius Zimand

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
A fundamental question that has been studied in cryptography and in information theory is whether two parties can communicate confidentially using exclusively an open channel. We consider the model in which the two parties hold inputs that are correlated in a certain sense. This model has been studied extensively in information theory, and communication protocols have been designed which exploit the correlation to extract from the inputs a shared secret key. However, all the existing protocols are not universal in the sense that they require that the two parties also know some attributes of the correlation. In other words, they require that each party knows something about the other party’s input. We present a protocol that does not require any prior additional information. It uses space-bounded Kolmogorov complexity to measure correlation and it allows the two legal parties to obtain a common key that looks random to an eavesdropper that observes the communication and is restricted to use a bounded amount of space for the attack. Thus the protocol achieves complexity-theoretical security, but it does not use any unproven result from computational complexity. On the negative side, the protocol is not efficient in the sense that the computation of the two legal parties uses more space than the space allowed to the adversary.
Cite as

Marius Zimand. Secret Key Agreement from Correlated Data, with No Prior Information. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zimand:LIPIcs.STACS.2020.21,
  author =	{Zimand, Marius},
  title =	{{Secret Key Agreement from Correlated Data, with No Prior Information}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.21},
  URN =		{urn:nbn:de:0030-drops-118823},
  doi =		{10.4230/LIPIcs.STACS.2020.21},
  annote =	{Keywords: secret key agreement, Kolmogorov complexity, extractors}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.95
An Operational Characterization of Mutual Information in Algorithmic Information Theory

Authors: Andrei Romashchenko and Marius Zimand

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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

Andrei Romashchenko and Marius Zimand. An Operational Characterization of Mutual Information in Algorithmic Information Theory. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 95:1-95:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{romashchenko_et_al:LIPIcs.ICALP.2018.95,
  author =	{Romashchenko, Andrei and Zimand, Marius},
  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 =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.95},
  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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.58
List Approximation for Increasing Kolmogorov Complexity

Authors: Marius Zimand

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. But is it possible to construct a few strings, not longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that on input a string x of length n returns a list with O(n^2) many strings, all of length n, such that 99% of them are more complex than x, provided the complexity of x is less than n. We obtain similar results for other parameters, including a polynomial-time construction.
Cite as

Marius Zimand. List Approximation for Increasing Kolmogorov Complexity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 58:1-58:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{zimand:LIPIcs.STACS.2017.58,
  author =	{Zimand, Marius},
  title =	{{List Approximation for Increasing Kolmogorov Complexity}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{58:1--58:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.58},
  URN =		{urn:nbn:de:0030-drops-70347},
  doi =		{10.4230/LIPIcs.STACS.2017.58},
  annote =	{Keywords: Kolmogorov complexity, list approximation, randomness extractor}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1812
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence

Authors: Marius Zimand

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
An infinite binary sequence has randomness rate at least $\sigma$ if, for almost every $n$, the Kolmogorov complexity of its prefix of length $n$ is at least $\sigma n$. It is known that for every rational $\sigma \in (0,1)$, on one hand, there exists sequences with randomness rate $\sigma$ that can not be effectively transformed into a sequence with randomness rate higher than $\sigma$ and, on the other hand, any two independent sequences with randomness rate $\sigma$ can be transformed into a sequence with randomness rate higher than $\sigma$. We show that the latter result holds even if the two input sequences have linear dependency (which, informally speaking, means that all prefixes of length $n$ of the two sequences have in common a constant fraction of their information). The similar problem is studied for finite strings. It is shown that from any two strings with sufficiently large Kolmogorov complexity and sufficiently small dependence, one can effectively construct a string that is random even conditioned by any one of the input strings.
Cite as

Marius Zimand. Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 697-708, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{zimand:LIPIcs.STACS.2009.1812,
  author =	{Zimand, Marius},
  title =	{{Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{697--708},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1812},
  URN =		{urn:nbn:de:0030-drops-18128},
  doi =		{10.4230/LIPIcs.STACS.2009.1812},
  annote =	{Keywords: Algorithmic information theory, Computational complexity, Kolmogorov complexity, Randomness extractors}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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