Randomized communication complexity of approximating Kolmogorov complexity

N. Vereshchagin

doi:10.1007/978-3-319-06686-8

Публикации

?

Randomized communication complexity of approximating Kolmogorov complexity

P. 365–374.

Верещагин Н. К.

Язык: английский

DOI

Ключевые слова: communication complexity Kolmogorov complexity

В книге

CSR 2014 : 9th International Computer Science Symposium in Russia. Proceedings

Vol. 8476. , Berlin: Springer, 2014.

О базовых математических определениях цифровых технологий и искусственного интеллекта

Семенов А. Л., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 527 № S С. 7–12

В работе предлагается система определений для основных понятия теории вычислимости, лежащих в основе математики цифрового мира: алгоритм, вычислимость, исчисление, сложность объекта, приближенная к современным представлениям. Рассматриваются иерархии конечного и проблема непротиворечивости. ...

Добавлено: 6 декабря 2025 г.

Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

Верещагин Н. К., Дектярев М. В., Математический сборник 2025 Т. 216 № 6 С. 3–45

Полудуплексная коммуникационная сложность с противником определена в работе [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В ...

Добавлено: 23 августа 2025 г.

Kolmogorov’s Last Discovery? (Kolmogorov and Algorithmic Statistics)

Семенов А. Л., Шень А., Верещагин Н. К., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606

Добавлено: 16 января 2025 г.

On information content in certain objects

Верещагин Н. К., / Series arXiv "math". 2024.

Добавлено: 19 августа 2024 г.

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Игнатьев А. А., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.

Добавлено: 9 ноября 2023 г.

Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time

Баувенс Б. Ф., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9

Добавлено: 22 марта 2023 г.

Inequalities for space-bounded Kolmogorov complexity

Баувенс Б. Ф., Gács P., Romashchenko A. и др., Computability 2022 Vol. 11 No. 3-4 P. 165–185

Добавлено: 23 декабря 2022 г.

Information disclosure in the framework of kolmogorov complexity

Верещагин Н. К., Theoretical Computer Science 2023 Vol. 940 P. 108–122

Добавлено: 19 декабря 2022 г.

Counting the Number of Perfect Matchings, and Generalized Decision Trees

Вялый М. Н., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160

Добавлено: 20 августа 2021 г.

Predictions and Algorithmic Statistics for Infinite Sequences

Милованов А. С., , in: Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings.: Springer, 2021. Ch. 17 P. 283–295.

Добавлено: 11 августа 2021 г.

The normalized algorithmic information distance can not be approximated

Баувенс Б. Ф., Блинников И. А., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 130–141.

Добавлено: 5 февраля 2021 г.

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

Подольский В. В., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26

Добавлено: 23 декабря 2020 г.

Information Distance Revisited

Баувенс Б. Ф., , in: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1–46:14.

Добавлено: 20 марта 2020 г.

Descriptive complexity of computable sequences revisited

Верещагин Н. К., Theoretical Computer Science 2020 Vol. 809 P. 531–537

Добавлено: 17 января 2020 г.

Algorithmic Statistics: Forty Years Later.

Shen A., Верещагин Н. К., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.

Добавлено: 26 октября 2018 г.

On Algorithmic Statistics for Space-bounded Algorithms

Милованов А. С., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848

Добавлено: 17 октября 2018 г.

Plain stopping time and conditional complexities revisited

Пособин Г. И., Shen A., Andreev M., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–24.

Добавлено: 11 октября 2018 г.

A Structural Lemma for Deterministic Context-Free Languages

Рубцов А. А., , in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings.: Cham: Springer, 2018. P. 553–565.

Добавлено: 12 сентября 2018 г.

Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms

Милованов А. С., , in: Sailing Routes in the World of Computation.: Springer, 2018. P. 287–296.

Добавлено: 4 сентября 2018 г.

One-Sided Error Communication Complexity of Gap Hamming Distance

Klenin E., Козачинский А. Н., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–15.

Добавлено: 28 августа 2018 г.

Euclidean Distance Matrices and Separations in Communication Complexity Theory

Шитов Я. Н., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653–660

Добавлено: 15 марта 2018 г.

On Algorithmic Statistics for Space-Bounded Algorithms

Милованов А. С., , in: Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017)Vol. 10304.: Luxemburg: Springer, 2017. P. 232–244.

Добавлено: 15 октября 2017 г.