×

Found 2,055 Documents (Results 101–200)

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI Link

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).
PDFBibTeX XMLCite
Full Text: DOI Link

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).
PDFBibTeX XMLCite
Full Text: DOI Link

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).
MSC:  68-01 68-02 68Q30
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software