Kolmogorov Complexity as a Combinatorial Tool

被引：0

作者：

Shen, Alexander ^{[1
]}

机构：

[1] Univ Montpellier, CNRS, LIRMM, Montpellier, France

来源：

TWENTY YEARS OF THEORETICAL AND PRACTICAL SYNERGIES, CIE 2024 | 2024年 / 14773卷

关键词：

Kolmogorov complexity; Combinatorial games; Experts aggregation;

D O I：

10.1007/978-3-031-64309-5_3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Kolmogorov complexity is often used as a convenient language for counting and/or probabilistic existence proofs. However, there are some applications where Kolmogorov complexity is used in a more subtle way. We provide one (somehow) surprising example where an existence of a winning strategy in a natural combinatorial game is proven (and no direct proof is known).

引用

页码：27 / 31

页数：5

共 10 条

[1] Partitioning multi-dimensional sets in a small number of "uniform" parts [J].

Alon, Noga ;

Newman, Ilan ;

Shen, Alexander ;

Tardos, Gabor ;

Vereshchagin, Nikolai .

EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (01) :134-144

[2] Complex tilings [J].

Durand, Bruno ;

Levin, Leonid A. ;

Shen, Alexander .

JOURNAL OF SYMBOLIC LOGIC, 2008, 73 (02) :593-613

[3]

Li M, 2008, ICCSE 2008: PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE & EDUCATION, P790

[4]

Muchnik An. A., 2010, PREPRINT, DOI [10.48550/arXiv.1003.4712, DOI 10.48550/ARXIV.1003.4712]

[5] An Operational Characterization of Mutual Information in Algorithmic Information Theory [J].

Romashchenko, Andrei ;

Zimand, Marius .

JOURNAL OF THE ACM, 2019, 66 (05)

[6]

Rosenfeld M, 2023, Arxiv, DOI arXiv:2204.00394

[7]

Rumyantsev AY, 2006, LECT NOTES COMPUT SC, V3884, P396

[8]

Shen Alexander, 2011, Computer Science - Theory and Applications. Proceedings of the 6th International Computer Science Symposium in Russia, CSR 2011, P105, DOI 10.1007/978-3-642-20712-9_9

[9]

Shen A., 2019, Kolmogorov complexity and algorithmic randomness, V220

[10] Compressibility and Probabilistic Proofs [J].

Shen, Alexander .

UNVEILING DYNAMICS AND COMPLEXITY, CIE 2017, 2017, 10307 :101-111

← 1 →