Rupert Hoelzl: Randomness in the Weihrauch degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 05 March 2014, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Rupert Hoelzl

Title: Randomness in the Weihrauch degrees

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: The Weihrauch degrees are a degree structure that can be used to
classify how complex it is to find solutions to certain mathematical
tasks, that typically arise from classical mathematical theorems, for
example in analysis. We will give an overview over recent work about
interactions between these degrees and the field of algorithmic
randomness. In particular we will discuss where two different models of
randomized computation are located in this lattice: computation with
access to a Martin-Löf random oracles and computation with a Las Vegas
algorithm. We will see that these two models can be separated in the
Weihrauch degree, which is in contrast to results in the related field
of reverse maths, where they are known to coincide. After briefly
discussing some other results relating the two subjects mentioned above,
we present some open questions.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.