×

Found 1,946 Documents (Results 1–100)

100
MathJax

Methods and applications of algorithmic complexity. Beyond statistical lossless compression. (English) Zbl 07503605

Emergence, Complexity and Computation 44. Berlin: Springer (ISBN 978-3-662-64983-1/hbk; 978-3-662-64985-5/ebook). ix, 267 p. (2022).
MSC:  68-02 68P30 68Q30
PDF BibTeX XML Cite
Full Text: DOI

Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report). (English) Zbl 07553911

Kostitsyna, Irina et al., Unconventional computation and natural computation. 19th international conference, UCNC 2021, Espoo, Finland, October 18–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12984, 177-193 (2021).
PDF BibTeX XML Cite
Full Text: DOI

On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \). (English) Zbl 07500821

Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12825, 11-40 (2021).
MSC:  68Q30 68P25 94A60
PDF BibTeX XML Cite
Full Text: DOI

Predictions and algorithmic statistics for infinite sequences. (English) Zbl 07493537

Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 283-295 (2021).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

On the meaning maximization doctrine: an alternative to the Utilitarian doctrine. (English) Zbl 1470.91106

Velupillai, Kumaraswamy (ed.), Keynesian, Sraffian, computable and dynamic economics. Theoretical and simulational (numerical) approaches. Cham: Palgrave Macmillan. 109-161 (2021).
MSC:  91B16
PDF BibTeX XML Cite
Full Text: DOI

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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
Full Text: DOI

Randomness and intractability in Kolmogorov complexity. (English) Zbl 07561525

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:  68Nxx 68Qxx
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
Full Text: DOI arXiv

Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts. (English) Zbl 07559132

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:  68Qxx
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
Full Text: DOI

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Classification

all top 3

Software