Oberseminar

Vorträge

27. Oktober 2009, 16 Uhr c.t., HS 134, AM

Liang Yu, Nanjing Unniversity
Something about Low (W2R, Kurtz)

3. November 2009, 16 Uhr c.t., HS 134, AM

Jason Constandas, Universität Heidelberg
Non-branching Q-Degrees

12. November 2009, 17 Uhr c.t., HS 134, AM

Jan Reimann, University of California, Berkeley
Old and news results on Algorithmic equivalence relations

24. November 2009, 16 Uhr c.t., HS 134, AM

John Hitchcock, University of Wyoming and CWI
Learnability, Randomness, and Lower Bounds

1. Dezember 2009, 16 Uhr c.t., HS 134, AM

Thorsten Kräling, Universität Heidelberg
Characterizations of randomness notions via prefix complexity

8. Dezember 2009, 16 Uhr c.t., HS 134, AM

Rupert Hölzl, Universität Heidelberg
Characterizations of randomness notions via prefix complexity, Part II

11. März 2010, 11 Uhr c.t., HS 134, AM

Serikzhan Badaev, Kazakh State University Almaty
Computable numberings in the Ershov hierarchy

19. März 2010, 11 Uhr c.t., HS 134, AM

Andre Nies, University of Auckland
Characterizing the K-trivial sets

Soemthing about Low (W2R, Kurtz)

As a step towards characterizing the class Low (W2R, Kurtz), we give an interesting sufficient condition

Non branching Q-Degrees

We give a brief introduction to Q-reducibility and then present the construction of a nonbranching c.e. Q-degree due to Downey, LaForte and Nies, which uses some interesting modifications to the analogous construction in the Turing degrees.

Old and news results on Algorithmic equivalence relations

Borel equivalence relations arising from recursion theoretic reducibilities seem to exhibit a stubborn resistance to complete classification. One reason may be seen in the fact that they relate to deep recursion theoretic problems, first and foremost Martin's Conjecture on degree invariant functions. I will present some recent progress on the classification of several recursion theoretic equivalence relations.

Learning, Randomness, and Lower Bounds

We describe two techniques for applying computational learning algorithms and resource-bounded randomness to obtain lower bounds in computational complexity. 1. The Winnow algorithm and other online mistake-bound learning algorithms are used to build martingales. This yields the solution of several open problems (Lutz and Mayordomo, 1994; Fu, 1994) about the density of hard sets for exponential time. 2. We connect exact learning via membership and equivalence queries to an extension of martingales called betting games. This allows us to relate the question of whether there is an exact learning algorithm for Boolean circuits to the question of whether exponential time has polynomial-size circuits, improving a result of Fortnow and Klivans (2009). This is joint work with Ryan Harkins.

Characterizations of Randomness Notions via Prefix Complexity

One of the basic theorems in algorithmic randomness theory says that Martin-Löf-randomness of a set A can be characterized by A having only incompressible initial segments (up to a compression of constantly many bits). This implies that for a non-Martin-Löf-random set we can for each number m find initial segments which are compressible by at least m bits. Here, finding these inital segments is effective relative to A. We will show that similar characterizations exist for other randomness notions as well, where we put our focus on strong randomness and 2-randomness. The basic question is: How much computing power do we need to find a prefix of A such that every longer prefix can be compressed by m bits? The talk will be continued next week with characterizations of further randomness notions.

Characterizations of Randomness Notions via Prefix Complexity, Part II

One of the basic theorems in algorithmic randomness theory says that Martin-Löf randomness of a set A can be characterized by A having only incompressible initial segments (up to a compression of constantly many bits). This implies that for a non-Martin-Löf-random set we can for each number m find initial segments which are compressible by at least m bits. Here, finding these inital segments is effective relative to A. We will show that similar characterizations exist for other randomness notions as well, where we put our focus on Martin-Löf randomness not below the halting problem and strong Kurtz randomness. The basic question is: How much computing power do we need to find a prefix of A such that every longer prefix can be compressed by m bits? This talk is the continuation of last week's talk. 

Characterizing the K-trivial sets

K-triviality is a property of sets expressing at the same time being far from random and being close to computable. Each K-trivial set is Delta_2 . The golden run method shows that a K-trivial set can be seen as a set where the total cost of changes is finite. The changes are measured via the standard cost function. We use the golden run method to show that a set A is K-trivial if and only if it obeys the simpler cost function c(x,s), namely the increase of the measure of the universal prefix free machine from stage x to s. The golden run method may also show that the class of sets with initial segment complexity bounded by a Solovay function coincides with the K-trivials.