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.
@InProceedings{brattka_et_al:LIPIcs.STACS.2015.130, author = {Brattka, Vasco and Gherardi, Guido and H\"{o}lzl, Rupert}, title = {{Las Vegas Computability and Algorithmic Randomness}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {130--142}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.130}, URN = {urn:nbn:de:0030-drops-49093}, doi = {10.4230/LIPIcs.STACS.2015.130}, annote = {Keywords: Weihrauch degrees, weak weak K\"{o}nig's lemma, Las Vegas computability, algorithmic randomness, Nash equilibria} }
Feedback for Dagstuhl Publishing