Document Open Access Logo

Las Vegas Computability and Algorithmic Randomness

Authors Vasco Brattka, Guido Gherardi, Rupert Hölzl

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.130.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Vasco Brattka
Guido Gherardi
Rupert Hölzl

Cite As Get BibTex

Vasco Brattka, Guido Gherardi, and Rupert Hölzl. Las Vegas Computability and Algorithmic Randomness. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 130-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.130

Abstract

In this article we try to formalize the question "What can be computed with access to randomness?" We propose the very fine-grained Weihrauch lattice as an approach to differentiate between different types of computation with access to randomness. In particular, we show that a natural concept of Las Vegas computability on infinite objects is more powerful than mere oracle access to a Martin-Löf random object. As a concrete problem that is Las Vegas computable but not computable with access to a Martin-Löf random oracle we study the problem of finding Nash equilibria.

Subject Classification

Keywords
  • Weihrauch degrees
  • weak weak König's lemma
  • Las Vegas computability
  • algorithmic randomness
  • Nash equilibria

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM Journal on Computing, 35(6):1467-1493, 2006. Google Scholar
  2. Jeremy Avigad, Edward T. Dean, and Jason Rute. Algorithmic randomness, reverse mathematics, and the dominated convergence theorem. Annals of Pure and Applied Logic, 163(12):1854-1864, 2012. Google Scholar
  3. László Babai. Monte-Carlo algorithms in graph isomorphism testing. Technical Report No. 79-10, Université de Montréal, Département de Mathématique et de Statistique, 1979. Google Scholar
  4. Vasco Brattka, Matthew de Brecht, and Arno Pauly. Closed choice and a uniform low basis theorem. Annals of Pure and Applied Logic, 163(8):986-1008, 2012. Google Scholar
  5. Vasco Brattka and Guido Gherardi. Effective choice and boundedness principles in computable analysis. The Bulletin of Symbolic Logic, 17(1):73-117, 2011. Google Scholar
  6. Vasco Brattka and Guido Gherardi. Weihrauch degrees, omniscience principles and weak computability. The Journal of Symbolic Logic, 76(1):143-176, 2011. Google Scholar
  7. Vasco Brattka, Guido Gherardi, and Rupert Hölzl. Probabilistic computability and choice. July 2014. Preliminary version available at http://arxiv.org/abs/1312.7305. Google Scholar
  8. Vasco Brattka, Guido Gherardi, and Alberto Marcone. The Bolzano-Weierstrass theorem is the jump of weak Kőnig’s lemma. Annals of Pure and Applied Logic, 163(6):623-655, 2012. Google Scholar
  9. Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. On the uniform computational content of computability theory. January 2015. Preliminary version available at http://arxiv.org/abs/1501.00433. Google Scholar
  10. Vasco Brattka and Arno Pauly. Computation with advice. In Xizhong Zheng and Ning Zhong, editors, CCA 2010, Proceedings of the Seventh International Conference on Computability and Complexity in Analysis, Electronic Proceedings in Theoretical Computer Science, pages 41-55, 2010. Google Scholar
  11. François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer. On uniform relationships between combinatorial problems. Transactions of the AMS, 2014. Accepted for publication. Preliminary version available at http://arxiv.org/abs/1212.0157. Google Scholar
  12. Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010. Google Scholar
  13. Guido Gherardi and Alberto Marcone. How incomputable is the separable Hahn-Banach theorem? Notre Dame Journal of Formal Logic, 50(4):393-425, 2009. Google Scholar
  14. Antonín Kučera. Measure, Π⁰₁-classes and complete extensions of PA. In Heinz-Dieter Ebbinghaus, Gert H. Müller, and Gerald E. Sacks, editors, Recursion Theory Week. Proceedings of the Conference Held at the Mathematisches Forschungsinstitut in Oberwolfach, April 15-21, 1984, volume 1141 of Lecture Notes in Mathematics, pages 245-259. Springer, Berlin, 1985. Google Scholar
  15. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995. Google Scholar
  16. John Nash. Non-cooperative games. Annals of Mathematics, 54:286-295, 1951. Google Scholar
  17. André Nies. Computability and Randomness, volume 51 of Oxford Logic Guides. Oxford University Press, New York, 2009. Google Scholar
  18. Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, Cambridge, 2007. Google Scholar
  19. Arno Pauly. How incomputable is finding Nash equilibria? Journal of Universal Computer Science, 16(18):2686-2710, 2010. Google Scholar
  20. Arno Pauly. On the (semi)lattices induced by continuous reducibilities. Mathematical Logic Quarterly, 56(5):488-502, 2010. Google Scholar
  21. Arno Pauly. Computable Metamathematics and its Application to Game Theory. PhD thesis, University of Cambridge, Computer Laboratory, Clare College, Cambridge, 2011. Google Scholar
  22. Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Logic, Association for Symbolic Logic. Cambridge University Press, Poughkeepsie, 2009. Google Scholar
  23. Nazanin R. Tavana and Klaus Weihrauch. Turing machines on represented sets, a model of computation for analysis. Logical Methods in Computer Science, 7(2:19):1-21, 2011. Google Scholar
  24. Klaus Weihrauch. The degrees of discontinuity of some translators between representations of the real numbers. Technical Report TR-92-050, International Computer Science Institute, Berkeley, July 1992. Google Scholar
  25. Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000. Google Scholar
  26. Martin Ziegler. Real hypercomputation and continuity. Theory of Computing Systems, 41(1):177-206, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact