Barmpalias, George; Lewis-Pye, Andrew Limits of the Kučera-Gács coding method. (English) Zbl 1528.03179 Cenzer, Douglas (ed.) et al., Structure and randomness in computability and set theory. Hackensack, NJ: World Scientific. 87-109 (2021). MSC: 03D32 68Q30 PDFBibTeX XMLCite \textit{G. Barmpalias} and \textit{A. Lewis-Pye}, in: Structure and randomness in computability and set theory. Hackensack, NJ: World Scientific. 87--109 (2021; Zbl 1528.03179) Full Text: DOI arXiv
Arslanov, M. M. Fixed-point selection functions. (English) Zbl 1491.03030 Lobachevskii J. Math. 42, No. 4, 685-692 (2021). MSC: 03D25 03D30 68Q30 PDFBibTeX XMLCite \textit{M. M. Arslanov}, Lobachevskii J. Math. 42, No. 4, 685--692 (2021; Zbl 1491.03030) Full Text: DOI
Kozachinskiy, Alexander; Shen, Alexander Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. (English) Zbl 1505.68018 J. Comput. Syst. Sci. 118, 75-107 (2021). Reviewer: Ludwig Staiger (Halle) MSC: 68Q30 68Q45 PDFBibTeX XMLCite \textit{A. Kozachinskiy} and \textit{A. Shen}, J. Comput. Syst. Sci. 118, 75--107 (2021; Zbl 1505.68018) Full Text: DOI arXiv
Agüero Trejo, José Manuel; Calude, Cristian S. A new quantum random number generator certified by value indefiniteness. (English) Zbl 1497.68232 Theor. Comput. Sci. 862, 3-13 (2021). MSC: 68Q30 68Q12 81P68 PDFBibTeX XMLCite \textit{J. M. Agüero Trejo} and \textit{C. S. Calude}, Theor. Comput. Sci. 862, 3--13 (2021; Zbl 1497.68232) Full Text: DOI arXiv
Du, Ding-Zhu (ed.); Wang, Jie (ed.) Editorial: Complexity and approximation: in honor of Ker-I Ko. (English) Zbl 1477.68011 Theor. Comput. Sci. 858, 143 (2021). MSC: 68-06 00B15 00B30 01A70 68Q30 68W25 PDFBibTeX XMLCite \textit{D.-Z. Du} (ed.) and \textit{J. Wang} (ed.), Theor. Comput. Sci. 858, 143 (2021; Zbl 1477.68011) Full Text: DOI
Vereshchagin, Nikolay Proofs of conservation inequalities for Levin’s notion of mutual information of 1974. (English) Zbl 1471.68097 Theor. Comput. Sci. 856, 14-20 (2021). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 68Q30 PDFBibTeX XMLCite \textit{N. Vereshchagin}, Theor. Comput. Sci. 856, 14--20 (2021; Zbl 1471.68097) Full Text: DOI arXiv
Kjos-Hanssen, Bjørn Automatic complexity of Fibonacci and tribonacci words. (English) Zbl 1477.68134 Discrete Appl. Math. 289, 446-454 (2021). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 68Q30 68Q45 68R15 PDFBibTeX XMLCite \textit{B. Kjos-Hanssen}, Discrete Appl. Math. 289, 446--454 (2021; Zbl 1477.68134) Full Text: DOI arXiv
Barmpalias, George; Liu, Lu Irreducibility of enumerable betting strategies. arXiv:2112.14416 Preprint, arXiv:2112.14416 [math.PR] (2021). MSC: 03D80 68Q30 03D32 BibTeX Cite \textit{G. Barmpalias} and \textit{L. Liu}, ``Irreducibility of enumerable betting strategies'', Preprint, arXiv:2112.14416 [math.PR] (2021) Full Text: arXiv OA License
Nies, André; Stephan, Frank Randomness and initial segment complexity for probability measures. (English) Zbl 07650940 Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 55, 14 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Nies} and \textit{F. Stephan}, LIPIcs -- Leibniz Int. Proc. Inform. 154, Article 55, 14 p. (2020; Zbl 07650940) Full Text: DOI
Bauwens, Bruno Information distance revisited. (English) Zbl 07650931 Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 46, 14 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{B. Bauwens}, LIPIcs -- Leibniz Int. Proc. Inform. 154, Article 46, 14 p. (2020; Zbl 07650931) Full Text: DOI
Zimand, Marius Secret key agreement from correlated data, with no prior information. (English) Zbl 07650906 Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 21, 12 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. Zimand}, LIPIcs -- Leibniz Int. Proc. Inform. 154, Article 21, 12 p. (2020; Zbl 07650906) Full Text: DOI arXiv
Persiau, Floris; De Bock, Jasper; de Cooman, Gert Computable randomness is about more than probabilities. (English) Zbl 1517.68149 Davis, Jesse (ed.) et al., Scalable uncertainty management. 14th international conference, SUM 2020, Bozen-Bolzano, Italy, September 23–25, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12322, 172-186 (2020). MSC: 68Q30 60A99 60G48 PDFBibTeX XMLCite \textit{F. Persiau} et al., Lect. Notes Comput. Sci. 12322, 172--186 (2020; Zbl 1517.68149) Full Text: DOI arXiv
Bauwens, Bruno; Blinnikov, Ilya The normalized algorithmic information distance can not be approximated. (English) Zbl 07603917 Fernau, Henning, Computer science – theory and applications. 15th international computer science symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12159, 130-141 (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{B. Bauwens} and \textit{I. Blinnikov}, Lect. Notes Comput. Sci. 12159, 130--141 (2020; Zbl 07603917) Full Text: DOI arXiv
Chaitin, Gregory Consciousness and information, classical, quantum or algorithmic? (English) Zbl 1496.00024 de Barros, J. Acacio (ed.) et al., A true polymath. A tribute to Francisco Antonio Doria. Based on the meeting, Rio de Janeiro, Brazil, December 2018. [s.l.]: College Publications. Acad. Bras. Filos. 2, 260-269 (2020). MSC: 00A30 68Q30 PDFBibTeX XMLCite \textit{G. Chaitin}, Acad. Bras. Filos. 2, 260--269 (2020; Zbl 1496.00024)
Gürpınar, Emirhan; Romashchenko, Andrei Communication complexity of the secret key agreement in algorithmic information theory. (English) Zbl 07559415 Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 44, 14 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{E. Gürpınar} and \textit{A. Romashchenko}, LIPIcs -- Leibniz Int. Proc. Inform. 170, Article 44, 14 p. (2020; Zbl 07559415) Full Text: DOI arXiv
Bickel, David R. Confidence intervals, significance values, maximum likelihood estimates, etc. sharpened into Occam’s razors. (English) Zbl 1511.62007 Commun. Stat., Theory Methods 49, No. 11, 2703-2712 (2020). MSC: 62A01 62F15 62F25 PDFBibTeX XMLCite \textit{D. R. Bickel}, Commun. Stat., Theory Methods 49, No. 11, 2703--2712 (2020; Zbl 1511.62007) Full Text: DOI HAL
Aksentijevic, A.; Mihailović, D. T.; Kapor, D.; Crvenković, S.; Nikolic-Djorić, E.; Mihailović, A. Complementarity of information obtained by Kolmogorov and Aksentijevic-Gibson complexities in the analysis of binary time series. (English) Zbl 1489.94048 Chaos Solitons Fractals 130, Article ID 109394, 16 p. (2020). MSC: 94A17 68Q30 62M10 91B84 94A15 PDFBibTeX XMLCite \textit{A. Aksentijevic} et al., Chaos Solitons Fractals 130, Article ID 109394, 16 p. (2020; Zbl 1489.94048) Full Text: DOI
Dinur, Itai On the streaming indistinguishability of a random permutation and a random function. (English) Zbl 1492.94090 Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12106, 433-460 (2020). MSC: 94A60 68Q30 PDFBibTeX XMLCite \textit{I. Dinur}, Lect. Notes Comput. Sci. 12106, 433--460 (2020; Zbl 1492.94090) Full Text: DOI
Antonopoulou, Hera Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT. (English) Zbl 1508.68135 J. Discrete Math. Sci. Cryptography 23, No. 7, 1431-1438 (2020). MSC: 68Q30 68T20 PDFBibTeX XMLCite \textit{H. Antonopoulou}, J. Discrete Math. Sci. Cryptography 23, No. 7, 1431--1438 (2020; Zbl 1508.68135) Full Text: DOI
Skums, Pavel; Bunimovich, Leonid Graph fractal dimension and the structure of fractal networks. (English) Zbl 1481.90099 J. Complex Netw. 8, No. 4, Article ID cnaa037, 24 p. (2020). MSC: 90B10 PDFBibTeX XMLCite \textit{P. Skums} and \textit{L. Bunimovich}, J. Complex Netw. 8, No. 4, Article ID cnaa037, 24 p. (2020; Zbl 1481.90099) Full Text: DOI Link
Devine, Sean D. Algorithmic information theory for physicists and natural scientists. (English) Zbl 1508.68006 Bristol: IOP Publishing (ISBN 978-0-7503-2638-4/print; 978-0-7503-2640-7/ebook). xiii, 12 chapters, not consecutively paged (2020). MSC: 68-01 00A06 68Q30 PDFBibTeX XMLCite \textit{S. D. Devine}, Algorithmic information theory for physicists and natural scientists. Bristol: IOP Publishing (2020; Zbl 1508.68006) Full Text: DOI
Downey, Rod Randomness and computation. (English) Zbl 1505.03089 Rezuş, Adrian (ed.), Contemporary logic and computing. London: College Publications. Landsc. Log. 1, 468-517 (2020). MSC: 03D32 68Q30 PDFBibTeX XMLCite \textit{R. Downey}, Landsc. Log. 1, 468--517 (2020; Zbl 1505.03089)
Winter, Michael Meta+phenomenology: primer towards a phenomenology formally based on algorithmic information theory and metabiology. (English) Zbl 1527.68094 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 317-334 (2020). MSC: 68Q30 92B05 PDFBibTeX XMLCite \textit{M. Winter}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 317--334 (2020; Zbl 1527.68094) Full Text: DOI
Walker, Sara Imari; Davies, Paul C. W. From the origins of life to the nature of intelligence. (English) Zbl 1527.92032 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 289-315 (2020). MSC: 92D15 03A10 68Q30 68Q80 PDFBibTeX XMLCite \textit{S. I. Walker} and \textit{P. C. W. Davies}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 289--315 (2020; Zbl 1527.92032) Full Text: DOI
Acacio de Barros, J. On information, quanta, and context. (English) Zbl 1527.68092 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 239-270 (2020). MSC: 68Q30 81P13 81P45 94A15 94A17 PDFBibTeX XMLCite \textit{J. Acacio de Barros}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 239--270 (2020; Zbl 1527.68092) Full Text: DOI
Zenil, Hector Compression is comprehension and the unreasonable effectiveness of digital computation in the natural world. (English) Zbl 1527.03006 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 201-238 (2020). MSC: 03A10 03D32 68Q30 68Q80 PDFBibTeX XMLCite \textit{H. Zenil}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 201--238 (2020; Zbl 1527.03006) Full Text: DOI arXiv
Abrahão, Felipe S.; D’Ottaviano, Ítala M. L.; Wehmuth, Klaus; Doria, Francisco Antonio; Ziviani, Artur Learning the undecidable from networked systems. (English) Zbl 1527.68061 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 131-179 (2020). MSC: 68Q01 68Q10 68Q30 PDFBibTeX XMLCite \textit{F. S. Abrahão} et al., in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 131--179 (2020; Zbl 1527.68061) Full Text: DOI arXiv
Pagallo, Ugo Rules, networks, and evolution: on Chaitin’s algorithmic information theory and the threefold complexity of the law. (English) Zbl 1527.03005 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 107-130 (2020). MSC: 03A10 68Q30 PDFBibTeX XMLCite \textit{U. Pagallo}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 107--130 (2020; Zbl 1527.03005) Full Text: DOI
Sangalli, Arturo Literature and mathematics: Jorge Luis Borges’ library and Gregory Chaitin’s Omega. (English) Zbl 1527.00002 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 83-89 (2020). MSC: 00A64 03D32 68Q30 PDFBibTeX XMLCite \textit{A. Sangalli}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 83--89 (2020; Zbl 1527.00002) Full Text: DOI
Chaitin, Gregory Conceptual complexity and algorithmic information. (English) Zbl 1527.68093 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 21-40 (2020). MSC: 68Q30 03A05 PDFBibTeX XMLCite \textit{G. Chaitin}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 21--40 (2020; Zbl 1527.68093) Full Text: DOI
Chaitin, Gregory An experiment in autobiography. (English) Zbl 1527.68004 Wuppuluri, Shyam (ed.) et al., Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 1-14 (2020). MSC: 68-03 01A70 03D32 68Q30 PDFBibTeX XMLCite \textit{G. Chaitin}, in: Unravelling complexity. The life and work of Gregory Chaitin. Hackensack, NJ: World Scientific. 1--14 (2020; Zbl 1527.68004) Full Text: DOI
Kjos-Hanssen, Bjørn; Liu, Lu Extracting randomness within a subset is hard. (English) Zbl 1467.68075 Eur. J. Math. 6, No. 4, 1438-1451 (2020). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q30 03D32 03D80 28A78 PDFBibTeX XMLCite \textit{B. Kjos-Hanssen} and \textit{L. Liu}, Eur. J. Math. 6, No. 4, 1438--1451 (2020; Zbl 1467.68075) Full Text: DOI
Kumabe, Masahiro; Miyabe, Kenshi; Mizusawa, Yuki; Suzuki, Toshio Solovay reducibility and continuity. (English) Zbl 1472.03041 J. Log. Anal. 12, Paper No. 2, 22 p. (2020). Reviewer: Liang Yu (Nanjing) MSC: 03D78 03D32 68Q30 PDFBibTeX XMLCite \textit{M. Kumabe} et al., J. Log. Anal. 12, Paper No. 2, 22 p. (2020; Zbl 1472.03041) Full Text: DOI arXiv
Hirahara, Shuichi Unexpected hardness results for Kolmogorov complexity under uniform reductions. (English) Zbl 07298308 Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1038-1051 (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{S. Hirahara}, in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1038--1051 (2020; Zbl 07298308) Full Text: DOI
Elze, Hans-Thomas Are quantum spins but small perturbations of ontological Ising spins? (English) Zbl 1454.81019 Found. Phys. 50, No. 12, 1875-1893 (2020). MSC: 81P05 68Q30 17B81 82C20 PDFBibTeX XMLCite \textit{H.-T. Elze}, Found. Phys. 50, No. 12, 1875--1893 (2020; Zbl 1454.81019) Full Text: DOI arXiv
Epstein, Samuel An extended coding theorem with application to quantum complexities. (English) Zbl 1496.68159 Inf. Comput. 275, Article ID 104660, 13 p. (2020). MSC: 68Q30 68Q12 PDFBibTeX XMLCite \textit{S. Epstein}, Inf. Comput. 275, Article ID 104660, 13 p. (2020; Zbl 1496.68159) Full Text: DOI arXiv
Lutz, Neil; Stull, D. M. Bounding the dimension of points on a line. (English) Zbl 1496.68160 Inf. Comput. 275, Article ID 104601, 16 p. (2020). MSC: 68Q30 28A80 PDFBibTeX XMLCite \textit{N. Lutz} and \textit{D. M. Stull}, Inf. Comput. 275, Article ID 104601, 16 p. (2020; Zbl 1496.68160) Full Text: DOI arXiv
Calude, Cristian S.; Dumitrescu, Monica A statistical anytime algorithm for the halting problem. (English) Zbl 1485.68119 Computability 9, No. 2, 155-166 (2020). MSC: 68Q30 60E15 62G30 68Q87 68W40 PDFBibTeX XMLCite \textit{C. S. Calude} and \textit{M. Dumitrescu}, Computability 9, No. 2, 155--166 (2020; Zbl 1485.68119) Full Text: DOI
Frongillo, Rafael; Nobel, Andrew Memoryless sequences for general losses. (English) Zbl 1499.68155 J. Mach. Learn. Res. 21, Paper No. 80, 28 p. (2020). MSC: 68Q30 91B26 PDFBibTeX XMLCite \textit{R. Frongillo} and \textit{A. Nobel}, J. Mach. Learn. Res. 21, Paper No. 80, 28 p. (2020; Zbl 1499.68155) Full Text: Link
Liu, Yi; Huang, Pengfei; Bergman, Alexander W.; Siegel, Paul H. Rate-constrained shaping codes for structured sources. (English) Zbl 1446.94061 IEEE Trans. Inf. Theory 66, No. 8, 5261-5281 (2020). MSC: 94A29 68Q30 PDFBibTeX XMLCite \textit{Y. Liu} et al., IEEE Trans. Inf. Theory 66, No. 8, 5261--5281 (2020; Zbl 1446.94061) Full Text: DOI arXiv
Wei, Yuting; Fang, Billy; Wainwright, Martin J. From Gauss to Kolmogorov: localized measures of complexity for ellipses. (English) Zbl 1448.62023 Electron. J. Stat. 14, No. 2, 2988-3031 (2020). MSC: 62B10 62B11 60A10 68Q30 PDFBibTeX XMLCite \textit{Y. Wei} et al., Electron. J. Stat. 14, No. 2, 2988--3031 (2020; Zbl 1448.62023) Full Text: DOI arXiv Euclid
Gavinsky, Dmitry; Pudlák, Pavel Santha-Vazirani sources, deterministic condensers and very strong extractors. (English) Zbl 1476.68081 Theory Comput. Syst. 64, No. 6, 1140-1154 (2020). MSC: 68P30 68Q30 PDFBibTeX XMLCite \textit{D. Gavinsky} and \textit{P. Pudlák}, Theory Comput. Syst. 64, No. 6, 1140--1154 (2020; Zbl 1476.68081) Full Text: DOI arXiv
Cohen, Albert; Dahmen, Wolfgang; Devore, Ronald; Nichols, James Reduced basis greedy selection using random training sets. (English) Zbl 1444.62113 ESAIM, Math. Model. Numer. Anal. 54, No. 5, 1509-1524 (2020). MSC: 62M45 65D05 65Y20 68Q32 68Q30 35B30 41A25 58D15 PDFBibTeX XMLCite \textit{A. Cohen} et al., ESAIM, Math. Model. Numer. Anal. 54, No. 5, 1509--1524 (2020; Zbl 1444.62113) Full Text: DOI arXiv
Allender, Eric The new complexity landscape around circuit minimization. (English) Zbl 1437.68059 Leporati, Alberto (ed.) et al., Language and automata theory and applications. 14th international conference, LATA 2020, Milan, Italy, March 4–6, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12038, 3-16 (2020). MSC: 68Q06 68Q30 PDFBibTeX XMLCite \textit{E. Allender}, Lect. Notes Comput. Sci. 12038, 3--16 (2020; Zbl 1437.68059) Full Text: DOI
Hirahara, Shuichi; Watanabe, Osamu On nonadaptive reductions to the set of random strings and its dense subsets. (English) Zbl 1440.68142 Du, Ding-Zhu (ed.) et al., Complexity and approximation. In memory of Ker-I Ko. Cham: Springer. Lect. Notes Comput. Sci. 12000, 67-79 (2020). MSC: 68Q30 68Q25 PDFBibTeX XMLCite \textit{S. Hirahara} and \textit{O. Watanabe}, Lect. Notes Comput. Sci. 12000, 67--79 (2020; Zbl 1440.68142) Full Text: DOI
Lutz, Jack H.; Lutz, Neil Who asked us? How the theory of computing answers questions about analysis. (English) Zbl 1440.68144 Du, Ding-Zhu (ed.) et al., Complexity and approximation. In memory of Ker-I Ko. Cham: Springer. Lect. Notes Comput. Sci. 12000, 48-56 (2020). MSC: 68Q30 28A80 28-02 68-02 PDFBibTeX XMLCite \textit{J. H. Lutz} and \textit{N. Lutz}, Lect. Notes Comput. Sci. 12000, 48--56 (2020; Zbl 1440.68144) Full Text: DOI arXiv
Allender, Eric Ker-I Ko and the study of resource-bounded Kolmogorov complexity. (English) Zbl 1440.68141 Du, Ding-Zhu (ed.) et al., Complexity and approximation. In memory of Ker-I Ko. Cham: Springer. Lect. Notes Comput. Sci. 12000, 8-18 (2020). MSC: 68Q30 68-03 68Q25 PDFBibTeX XMLCite \textit{E. Allender}, Lect. Notes Comput. Sci. 12000, 8--18 (2020; Zbl 1440.68141) Full Text: DOI
Jordon, Liam; Moser, Philippe On the difference between finite-state and pushdown depth. (English) Zbl 1440.68143 Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 187-198 (2020). MSC: 68Q30 PDFBibTeX XMLCite \textit{L. Jordon} and \textit{P. Moser}, Lect. Notes Comput. Sci. 12011, 187--198 (2020; Zbl 1440.68143) Full Text: DOI
Tadaki, Kohtaro Algorithmic information theory and its statistical mechanical interpretation. (English. Japanese original) Zbl 1455.68076 Sugaku Expo. 33, No. 1, 1-29 (2020); translation from Sūgaku 67, No. 1, 1-15 (2015). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q30 03D32 82B03 82B10 PDFBibTeX XMLCite \textit{K. Tadaki}, Sugaku Expo. 33, No. 1, 1--29 (2020; Zbl 1455.68076); translation from Sūgaku 67, No. 1, 1--15 (2015) Full Text: DOI
Staiger, Ludwig On the incomputability of computable dimension. (English) Zbl 1528.68151 Log. Methods Comput. Sci. 16, No. 2, Paper No. 5, 10 p. (2020). MSC: 68Q30 03D32 PDFBibTeX XMLCite \textit{L. Staiger}, Log. Methods Comput. Sci. 16, No. 2, Paper No. 5, 10 p. (2020; Zbl 1528.68151) Full Text: arXiv Link
Greenberg, Noam; Miller, Joseph S.; Nies, André Computing from projections of random points. (English) Zbl 1467.03013 J. Math. Log. 20, No. 1, Article ID 1950014, 41 p. (2020). Reviewer: Rupert Hölzl (Neubiberg) MSC: 03D32 68Q30 03D28 PDFBibTeX XMLCite \textit{N. Greenberg} et al., J. Math. Log. 20, No. 1, Article ID 1950014, 41 p. (2020; Zbl 1467.03013) Full Text: DOI arXiv
Landsman, Klaas Randomness? What randomness? (English) Zbl 1439.81009 Found. Phys. 50, No. 2, 61-104 (2020). MSC: 81P05 81P15 81Q65 81P94 68Q30 PDFBibTeX XMLCite \textit{K. Landsman}, Found. Phys. 50, No. 2, 61--104 (2020; Zbl 1439.81009) Full Text: DOI arXiv
Franklin, Johanna N. Y. (ed.); Porter, Christopher P. (ed.) Algorithmic randomness. Progress and prospects. (English) Zbl 1512.03019 Lecture Notes in Logic 50. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (ISBN 978-1-108-47898-4/hbk; 978-1-108-78171-8/ebook). x, 359 p. (2020). MSC: 03-06 03D32 68Q30 00B15 PDFBibTeX XMLCite \textit{J. N. Y. Franklin} (ed.) and \textit{C. P. Porter} (ed.), Algorithmic randomness. Progress and prospects. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (2020; Zbl 1512.03019) Full Text: DOI
Hölzl, Rupert; Merkle, Wolfgang; Miller, Joseph; Stephan, Frank; Yu, Liang Chaitin’s \(\Omega\) as a continuous function. (English) Zbl 1471.03068 J. Symb. Log. 85, No. 1, 486-510 (2020). Reviewer: Roman Murawski (Poznań) MSC: 03D32 68Q30 03D78 PDFBibTeX XMLCite \textit{R. Hölzl} et al., J. Symb. Log. 85, No. 1, 486--510 (2020; Zbl 1471.03068) Full Text: DOI
Nies, André; Shafer, Paul Randomness notions and reverse mathematics. (English) Zbl 1444.03013 J. Symb. Log. 85, No. 1, 271-299 (2020). Reviewer: Jeffry L. Hirst (Boone) MSC: 03B30 03D32 03F35 68Q30 PDFBibTeX XMLCite \textit{A. Nies} and \textit{P. Shafer}, J. Symb. Log. 85, No. 1, 271--299 (2020; Zbl 1444.03013) Full Text: DOI arXiv Link
Rojas, J. Maurice Book review of: A. Shen et al., Kolmogorov complexity and algorithmic randomness. (English) Zbl 1432.00019 Bull. Am. Math. Soc., New Ser. 57, No. 2, 339-346 (2020). MSC: 00A17 68-02 03-02 03D15 03D32 68Q19 68Q30 PDFBibTeX XMLCite \textit{J. M. Rojas}, Bull. Am. Math. Soc., New Ser. 57, No. 2, 339--346 (2020; Zbl 1432.00019) Full Text: DOI
Bauwens, Bruno Uniform van Lambalgen’s theorem fails for computable randomness. (English) Zbl 1441.68110 Inf. Comput. 271, Article ID 104486, 3 p. (2020). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 68Q30 03D32 60G48 PDFBibTeX XMLCite \textit{B. Bauwens}, Inf. Comput. 271, Article ID 104486, 3 p. (2020; Zbl 1441.68110) Full Text: DOI arXiv
Moser, Philippe Polylog depth, highness and lowness for E. (English) Zbl 1441.68112 Inf. Comput. 271, Article ID 104483, 10 p. (2020). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q30 03D15 68Q15 PDFBibTeX XMLCite \textit{P. Moser}, Inf. Comput. 271, Article ID 104483, 10 p. (2020; Zbl 1441.68112) Full Text: DOI arXiv
Barmpalias, George; Fang, Nan; Lewis-Pye, Andrew Monotonous betting strategies in warped casinos. (English) Zbl 1435.91044 Inf. Comput. 271, Article ID 104480, 18 p. (2020). MSC: 91A60 68Q30 PDFBibTeX XMLCite \textit{G. Barmpalias} et al., Inf. Comput. 271, Article ID 104480, 18 p. (2020; Zbl 1435.91044) Full Text: DOI arXiv
Du, Ding-Zhu (ed.); Wang, Jie (ed.) Complexity and approximation. In memory of Ker-I Ko. (English) Zbl 1435.68027 Lecture Notes in Computer Science 12000. Cham: Springer (ISBN 978-3-030-41671-3/pbk; 978-3-030-41672-0/ebook). x, 289 p. (2020). MSC: 68-06 68Q30 68W25 00B30 PDFBibTeX XMLCite \textit{D.-Z. Du} (ed.) and \textit{J. Wang} (ed.), Complexity and approximation. In memory of Ker-I Ko. Cham: Springer (2020; Zbl 1435.68027) Full Text: DOI
Bienvenu, Laurent; Csima, Barbara F.; Harrison-Trainor, Matthew Optimal bounds for single-source Kolmogorov extractors. (English) Zbl 1443.03022 Trans. Am. Math. Soc. 373, No. 3, 1983-2006 (2020). Reviewer: Rupert Hölzl (Neubiberg) MSC: 03D32 05C80 68Q30 PDFBibTeX XMLCite \textit{L. Bienvenu} et al., Trans. Am. Math. Soc. 373, No. 3, 1983--2006 (2020; Zbl 1443.03022) Full Text: DOI arXiv
Vereshchagin, Nikolay Descriptive complexity of computable sequences revisited. (English) Zbl 1443.68075 Theor. Comput. Sci. 809, 531-537 (2020). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q30 68Q19 PDFBibTeX XMLCite \textit{N. Vereshchagin}, Theor. Comput. Sci. 809, 531--537 (2020; Zbl 1443.68075) Full Text: DOI arXiv
Calude, Cristian S.; Jain, Sanjay; Merkle, Wolfgang; Stephan, Frank Searching for shortest and least programs. (English) Zbl 1443.68074 Theor. Comput. Sci. 807, 114-127 (2020). Reviewer: Liang Yu (Nanjing) MSC: 68Q30 03D10 PDFBibTeX XMLCite \textit{C. S. Calude} et al., Theor. Comput. Sci. 807, 114--127 (2020; Zbl 1443.68074) Full Text: DOI
Gilman, Robert Algorithmic search in group theory. (English) Zbl 1485.20083 J. Algebra 545, 237-244 (2020). MSC: 20F10 68Q30 20F05 PDFBibTeX XMLCite \textit{R. Gilman}, J. Algebra 545, 237--244 (2020; Zbl 1485.20083) Full Text: DOI arXiv
Liu, Lu The combinatorial equivalence of a computability theoretic question. arXiv:2012.13588 Preprint, arXiv:2012.13588 [math.LO] (2020). MSC: 03D80 68Q30 03D32 BibTeX Cite \textit{L. Liu}, ``The combinatorial equivalence of a computability theoretic question'', Preprint, arXiv:2012.13588 [math.LO] (2020) Full Text: arXiv OA License
Shen, Alexander Complexity of majorants. arXiv:2004.02844 Preprint, arXiv:2004.02844 [math.LO] (2020). MSC: 68Q30 BibTeX Cite \textit{A. Shen}, ``Complexity of majorants'', Preprint, arXiv:2004.02844 [math.LO] (2020) Full Text: arXiv OA License
Luchsinger, Austin; Schweller, Robert; Wylie, Tim Self-assembly of shapes at constant scale using repulsive forces. (English) Zbl 07802513 Nat. Comput. 18, No. 1, 93-105 (2019). MSC: 68Q09 68Q30 PDFBibTeX XMLCite \textit{A. Luchsinger} et al., Nat. Comput. 18, No. 1, 93--105 (2019; Zbl 07802513) Full Text: DOI
Oliveira, Igor Carboni; Pich, Ján; Santhanam, Rahul Hardness magnification near state-of-the-art lower bounds. (English) Zbl 1496.68155 Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 27, 29 p. (2019). MSC: 68Q17 68Q06 68Q30 PDFBibTeX XMLCite \textit{I. C. Oliveira} et al., LIPIcs -- Leibniz Int. Proc. Inform. 137, Article 27, 29 p. (2019; Zbl 1496.68155) Full Text: DOI
Oliveira, Igor Carboni Randomness and intractability in Kolmogorov complexity. (English) Zbl 1517.68148 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 32, 14 p. (2019). MSC: 68Q30 68P30 68Q06 68Q17 68W20 PDFBibTeX XMLCite \textit{I. C. Oliveira}, LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 32, 14 p. (2019; Zbl 1517.68148) Full Text: DOI
Posobin, Gleb; Shen, Alexander Random noise increases Kolmogorov complexity and Hausdorff dimension. (English) Zbl 07559166 Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 57, 14 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{G. Posobin} and \textit{A. Shen}, LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 57, 14 p. (2019; Zbl 07559166) Full Text: DOI arXiv
Destombes, Julien; Romashchenko, Andrei Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts. (English) Zbl 1503.68081 Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 23, 17 p. (2019). MSC: 68Q30 37B51 PDFBibTeX XMLCite \textit{J. Destombes} and \textit{A. Romashchenko}, LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 23, 17 p. (2019; Zbl 1503.68081) Full Text: DOI arXiv
Černý, Michal Narrow big data in a stream: computational limitations and regression. (English) Zbl 1454.62549 Inf. Sci. 486, 379-392 (2019). MSC: 62R07 62L12 68T09 PDFBibTeX XMLCite \textit{M. Černý}, Inf. Sci. 486, 379--392 (2019; Zbl 1454.62549) Full Text: DOI
Ishkuvatov, Ruslan; Musatov, Daniil On approximate uncomputability of the Kolmogorov complexity function. (English) Zbl 1434.68209 Manea, Florin (ed.) et al., Computing with foresight and industry. 15th conference on computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11558, 230-239 (2019). MSC: 68Q30 PDFBibTeX XMLCite \textit{R. Ishkuvatov} and \textit{D. Musatov}, Lect. Notes Comput. Sci. 11558, 230--239 (2019; Zbl 1434.68209) Full Text: DOI
Miyabe, Kenshi Uniform relativization. (English) Zbl 1434.03108 Manea, Florin (ed.) et al., Computing with foresight and industry. 15th conference on computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11558, 50-61 (2019). MSC: 03D32 68Q30 PDFBibTeX XMLCite \textit{K. Miyabe}, Lect. Notes Comput. Sci. 11558, 50--61 (2019; Zbl 1434.03108) Full Text: DOI
Sureson, Claude \(\Pi_1^1\)-Martin-Löf randomness and \(\Pi_1^1\)-Solovay completeness. (English) Zbl 1521.03130 Math. Log. Q. 65, No. 3, 265-279 (2019). MSC: 03D60 03D32 03E15 68Q30 PDFBibTeX XMLCite \textit{C. Sureson}, Math. Log. Q. 65, No. 3, 265--279 (2019; Zbl 1521.03130) Full Text: DOI
Kalociński, Dariusz; Steifer, Tomasz On unstable and unoptimal prediction. (English) Zbl 1521.03124 Math. Log. Q. 65, No. 2, 218-227 (2019). MSC: 03D32 68Q30 PDFBibTeX XMLCite \textit{D. Kalociński} and \textit{T. Steifer}, Math. Log. Q. 65, No. 2, 218--227 (2019; Zbl 1521.03124) Full Text: DOI
Merkle, Wolfgang; Yu, Liang Being low along a sequence and elsewhere. (English) Zbl 1443.03023 J. Symb. Log. 84, No. 2, 497-516 (2019). Reviewer: Leon Harkleroad (Bowdoinham) MSC: 03D32 68Q30 03D30 03D28 PDFBibTeX XMLCite \textit{W. Merkle} and \textit{L. Yu}, J. Symb. Log. 84, No. 2, 497--516 (2019; Zbl 1443.03023) Full Text: DOI
Alpeev, A. V. An announce of results linking Kolmogorov complexity to entropy for amenable group actions. (English) Zbl 1439.37032 J. Math. Sci., New York 240, No. 5, 503-506 (2019) and Zap. Nauchn. Semin. POMI 468, 7-12 (2018). Reviewer: Marta Macho Stadler (Leioa) MSC: 37C85 37A35 37B10 94A17 22D40 22F10 PDFBibTeX XMLCite \textit{A. V. Alpeev}, J. Math. Sci., New York 240, No. 5, 503--506 (2019; Zbl 1439.37032) Full Text: DOI
Romashchenko, Andrei; Zimand, Marius An operational characterization of mutual information in algorithmic information theory. (English) Zbl 1473.68100 J. ACM 66, No. 5, Article No. 38, 42 p. (2019). MSC: 68Q30 68Q11 94A60 PDFBibTeX XMLCite \textit{A. Romashchenko} and \textit{M. Zimand}, J. ACM 66, No. 5, Article No. 38, 42 p. (2019; Zbl 1473.68100) Full Text: DOI arXiv
Kozachinskiy, Alexander; Shen, Alexander Two characterizations of finite-state dimension. (English) Zbl 1511.68129 Gąsieniec, Leszek Antoni (ed.) et al., Fundamentals of computation theory. 22nd international symposium, FCT 2019, Copenhagen, Denmark, August 12–14, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11651, 80-94 (2019). MSC: 68Q30 11K16 68Q45 PDFBibTeX XMLCite \textit{A. Kozachinskiy} and \textit{A. Shen}, Lect. Notes Comput. Sci. 11651, 80--94 (2019; Zbl 1511.68129) Full Text: DOI Link
McKay, Dylan M.; Murray, Cody D.; Williams, R. Ryan Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. (English) Zbl 1434.68160 Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 1215-1225 (2019). MSC: 68Q06 68P30 68Q15 68Q17 68Q30 68W27 PDFBibTeX XMLCite \textit{D. M. McKay} et al., in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 1215--1225 (2019; Zbl 1434.68160) Full Text: DOI Link
Epstein, Samuel Algorithmic no-cloning theorem. (English) Zbl 1432.94043 IEEE Trans. Inf. Theory 65, No. 9, 5925-5930 (2019). MSC: 94A15 68Q30 PDFBibTeX XMLCite \textit{S. Epstein}, IEEE Trans. Inf. Theory 65, No. 9, 5925--5930 (2019; Zbl 1432.94043) Full Text: DOI arXiv
Millhouse, Tyler A simplicity criterion for physical computation. (English) Zbl 1428.68147 Br. J. Philos. Sci. 70, No. 1, 153-178 (2019). MSC: 68Q01 68Q30 PDFBibTeX XMLCite \textit{T. Millhouse}, Br. J. Philos. Sci. 70, No. 1, 153--178 (2019; Zbl 1428.68147) Full Text: DOI
Hölzl, Rupert; Porter, Christopher P. Rank and randomness. (English) Zbl 1454.03055 J. Symb. Log. 84, No. 4, 1527-1543 (2019). Reviewer: Liang Yu (Nanjing) MSC: 03D32 68Q30 PDFBibTeX XMLCite \textit{R. Hölzl} and \textit{C. P. Porter}, J. Symb. Log. 84, No. 4, 1527--1543 (2019; Zbl 1454.03055) Full Text: DOI arXiv
Allender, Eric; Hirahara, Shuichi New insights on the (non-)hardness of circuit minimization and related problems. (English) Zbl 1441.68081 ACM Trans. Comput. Theory 11, No. 4, Article No. 27, 27 p. (2019). MSC: 68Q25 68Q06 68Q17 68Q30 PDFBibTeX XMLCite \textit{E. Allender} and \textit{S. Hirahara}, ACM Trans. Comput. Theory 11, No. 4, Article No. 27, 27 p. (2019; Zbl 1441.68081) Full Text: DOI
Downey, Rod; Hirschfeldt, Denis R. Computability and randomness. (English) Zbl 1423.03145 Notices Am. Math. Soc. 66, No. 7, 1001-1012 (2019). MSC: 03D32 68Q30 PDFBibTeX XMLCite \textit{R. Downey} and \textit{D. R. Hirschfeldt}, Notices Am. Math. Soc. 66, No. 7, 1001--1012 (2019; Zbl 1423.03145) Full Text: DOI
Allender, Eric; Ilango, Rahul; Vafa, Neekon The non-hardness of approximating circuit size. (English) Zbl 1522.68193 van Bevern, René (ed.) et al., Computer science – theory and applications. 14th international computer science symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11532, 13-24 (2019). MSC: 68Q06 68Q17 68Q30 68W25 PDFBibTeX XMLCite \textit{E. Allender} et al., Lect. Notes Comput. Sci. 11532, 13--24 (2019; Zbl 1522.68193) Full Text: DOI Link
Downey, Rodney G.; Nandakumar, Satyadev; Nies, André Martin-Löf randomness implies multiple recurrence in effectively closed sets. (English) Zbl 07120752 Notre Dame J. Formal Logic 60, No. 3, 491-502 (2019). MSC: 03D32 37A30 68Q30 PDFBibTeX XMLCite \textit{R. G. Downey} et al., Notre Dame J. Formal Logic 60, No. 3, 491--502 (2019; Zbl 07120752) Full Text: DOI Euclid
Sdroievski, Nicollas M.; da Silva, Murilo V. G.; Vignatti, André L. The hidden subgroup problem and MKTP. (English) Zbl 1434.68203 Theor. Comput. Sci. 795, 204-212 (2019). MSC: 68Q25 20B35 20E07 68Q30 PDFBibTeX XMLCite \textit{N. M. Sdroievski} et al., Theor. Comput. Sci. 795, 204--212 (2019; Zbl 1434.68203) Full Text: DOI
Abrahão, Felipe S.; Wehmuth, Klaus; Ziviani, Artur Algorithmic networks: central time to trigger expected emergent open-endedness. (English) Zbl 1423.68222 Theor. Comput. Sci. 785, 83-116 (2019). MSC: 68Q30 05C82 68Q05 68Q10 PDFBibTeX XMLCite \textit{F. S. Abrahão} et al., Theor. Comput. Sci. 785, 83--116 (2019; Zbl 1423.68222) Full Text: DOI arXiv
Milovanov, Alexey On algorithmic statistics for space-bounded algorithms. (English) Zbl 1435.68129 Theory Comput. Syst. 63, No. 4, 833-848 (2019). MSC: 68Q30 62A01 68W20 PDFBibTeX XMLCite \textit{A. Milovanov}, Theory Comput. Syst. 63, No. 4, 833--848 (2019; Zbl 1435.68129) Full Text: DOI arXiv
Werschulz, A. G.; Woźniakowski, H. Tractability of multivariate approximation over weighted standard Sobolev spaces. (English) Zbl 1461.41004 J. Complexity 53, 95-112 (2019). MSC: 41A63 65Y20 68Q30 PDFBibTeX XMLCite \textit{A. G. Werschulz} and \textit{H. Woźniakowski}, J. Complexity 53, 95--112 (2019; Zbl 1461.41004) Full Text: DOI
Schweller, Robert; Winslow, Andrew; Wylie, Tim Nearly constant tile complexity for any shape in two-handed tile assembly. (English) Zbl 1425.68115 Algorithmica 81, No. 8, 3114-3135 (2019). MSC: 68Q05 68Q30 PDFBibTeX XMLCite \textit{R. Schweller} et al., Algorithmica 81, No. 8, 3114--3135 (2019; Zbl 1425.68115) Full Text: DOI
Moldagaliyev, Birzhan Randomness of formal languages via automatic martingales. (English) Zbl 1426.68151 Theor. Comput. Sci. 782, 113-128 (2019). Reviewer: Ludwig Staiger (Halle/Saale) MSC: 68Q45 60G48 68Q30 PDFBibTeX XMLCite \textit{B. Moldagaliyev}, Theor. Comput. Sci. 782, 113--128 (2019; Zbl 1426.68151) Full Text: DOI arXiv
Vitányi, Paul M. B. Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines. (English) Zbl 1423.68180 Theor. Comput. Sci. 778, 78-80 (2019). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q05 03D10 68Q30 PDFBibTeX XMLCite \textit{P. M. B. Vitányi}, Theor. Comput. Sci. 778, 78--80 (2019; Zbl 1423.68180) Full Text: DOI arXiv Link
Kjos-Hanssen, Bjørn Few paths, fewer words: model selection with automatic structure functions. (English) Zbl 1419.68057 Exp. Math. 28, No. 1, 121-127 (2019). Reviewer: Anatoliy Swishchuk (Calgary) MSC: 68Q30 62B10 68Q45 PDFBibTeX XMLCite \textit{B. Kjos-Hanssen}, Exp. Math. 28, No. 1, 121--127 (2019; Zbl 1419.68057) Full Text: DOI arXiv
Vitányi, P. M. B. Corrigendum to: “On the rate of decrease in logical depth” by by L. F. Antunes, A. Souto, and P. M. B. Vitányi. (English) Zbl 1421.68090 Theor. Comput. Sci. 770, 101 (2019). MSC: 68Q30 PDFBibTeX XMLCite \textit{P. M. B. Vitányi}, Theor. Comput. Sci. 770, 101 (2019; Zbl 1421.68090) Full Text: DOI
Li, Ming; Vitányi, Paul M. B. An introduction to Kolmogorov complexity and its applications. 4th revised and enhanced edition. (English) Zbl 1423.68005 Texts in Computer Science. Cham: Springer (ISBN 978-3-030-11297-4/hbk; 978-3-030-11298-1/ebook). xxii, 834 p. (2019). Reviewer: Ludwig Staiger (Halle/Saale) MSC: 68-01 68-02 68Q30 PDFBibTeX XMLCite \textit{M. Li} and \textit{P. M. B. Vitányi}, An introduction to Kolmogorov complexity and its applications. 4th revised and enhanced edition. Cham: Springer (2019; Zbl 1423.68005) Full Text: DOI
Liu, Lu Which DNR can be minimal. arXiv:1912.09053 Preprint, arXiv:1912.09053 [math.LO] (2019). MSC: 68Q30 BibTeX Cite \textit{L. Liu}, ``Which DNR can be minimal'', Preprint, arXiv:1912.09053 [math.LO] (2019) Full Text: arXiv OA License
Liu, Lu Avoid Schnorr randomness. arXiv:1912.09052 Preprint, arXiv:1912.09052 [math.LO] (2019). MSC: 68Q30 BibTeX Cite \textit{L. Liu}, ``Avoid Schnorr randomness'', Preprint, arXiv:1912.09052 [math.LO] (2019) Full Text: arXiv OA License