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.