The Library
Optimal coding theorems in time-bounded Kolmogorov complexity
Tools
Oliveira, Igor C., Lu, Zhenjian and Zimand, Marius (2022) Optimal coding theorems in time-bounded Kolmogorov complexity. In: 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), Paris ; Online, 4-8 Jul 2022. Published in: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), 229 92:1-92:14. ISBN 9783959772358. doi:10.4230/LIPIcs.ICALP.2022.92 ISSN 1868-8969.
|
PDF
WRAP-optimal-coding-theorems-time-bounded-Kolmogorov-complexity-2022.pdf - Accepted Version - Requires a PDF viewer. Download (614Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.92
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
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | 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): | Computational complexity , Computer science, Kolmogorov complexity , Coding theory, Machine theory | ||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||
Journal or Publication Title: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | ||||||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||||||||
ISBN: | 9783959772358 | ||||||||||||
ISSN: | 1868-8969 | ||||||||||||
Official Date: | 28 June 2022 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 229 | ||||||||||||
Page Range: | 92:1-92:14 | ||||||||||||
DOI: | 10.4230/LIPIcs.ICALP.2022.92 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 23 May 2022 | ||||||||||||
Date of first compliant Open Access: | 23 May 2022 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Paris ; Online | ||||||||||||
Date(s) of Event: | 4-8 Jul 2022 | ||||||||||||
Related URLs: | |||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year