The Library
Theory and applications of probabilistic Kolmogorov complexity
Tools
Lu, Zhenjian and Oliveira, Igor C. (2022) Theory and applications of probabilistic Kolmogorov complexity. Bulletin of EATCS, 137 .
|
PDF
WRAP-theory-applications-probabilistic-Kolmogorov-complexity-Oliveira-2022..pdf - Published Version - Requires a PDF viewer. Download (260Kb) | Preview |
|
PDF
WRAP-theory-applications-probabilistic-Kolmogorov-complexity-Oliveira-2022.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (599Kb) |
Official URL: http://bulletin.eatcs.org/index.php/beatcs/article...
Abstract
Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants of Kolmogorov complexity. While fruitful interactions between time-bounded Kolmogorov com- plexity and different areas of theoretical computer science have been known for quite a while (e.g., [Sip83, Ko91, ABK+ 06, AF09], to name a few), the aforementioned results have led to a renewed interest in this topic. The theory of Kolmogorov complexity is well understood, but many useful results and proper- ties of Kolmogorov complexity are not known to hold in time-bounded settings. Unfortunately, this creates technical diffculties or leads to conditional results when applying methods from time-bounded Kolmogorov complexity to algorithms and complexity theory. Perhaps even more importantly, in many cases it is desirable or even necessary to consider randomised algorithms. Since random strings have high complexity, the classical theory of time-bounded Kolmogorov complexity might be inappropriate or simply cannot be applied in such contexts. To mitigate these issues and develop a more robust theory of time-bounded Kolmogorov complexity that survives in the important setting of randomised computations, some recent papers [Oli19, LO21, LOS21, GKLO22, LOZ22] have explored probabilistic notions of time- bounded Kolmogorov complexity, such as rKt complexity [Oli19], rKt complexity [LOS21], and pKt complexity [GKLO22]. These measures consider different ways of encoding an object via a probabilistic representation. In this survey, we provide an introduction to probabilistic time- bounded Kolmogorov complexity and its applications, highlighting many open problems and research directions.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Kolmogorov complexity, Computational complexity, Information theory, Probabilities | ||||||
Journal or Publication Title: | Bulletin of EATCS | ||||||
Publisher: | European Association for Theoretical Computer Science | ||||||
Official Date: | June 2022 | ||||||
Dates: |
|
||||||
Volume: | 137 | ||||||
Number of Pages: | 44 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 20 May 2022 | ||||||
Date of first compliant Open Access: | 8 July 2022 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year