PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Randomness, partial relativization, and domination
Seminar:Logic Seminar
Speaker:George Barmpalias, Institute of Logic, Language, and Computation, University of Amsterdam
Abstract Link:
The first part is joint work with J. Miller and A. Nies and is concerned with highness notions that are based on notions from algorithmic randomness. For example, given two notions of randomness M, N (such that M is weaker than N) how strong should an oracle A be so that M relativized to A is stronger than N? We give characterizations of such classes of oracles for many formulations of randomness in terms of classical computability theoretic notions. Thus, we provide links between algorithmic randomness and classical computability theory. We focus on notions between 1-randomness and 2-randomness, with special attention to weak 2-randomness. The second part is joint work with R. Downey and S. Ng. The purpose of this work was to solve two questions from Nies' book concerning weakly 2-random sets. In doing so, it was necessary to develop a theory of jump inversion inside effectively closed sets. Amongst other results we provide a characterization of the jumps of the weakly 2-random sets which are not 2-random. Along with the results, we present a number of open questions.

Room Reservation Information

Room Number:MB315
Date:02 / 02 / 2010
Time:02:30pm - 03:45pm