back (Hompage - Dr. Christine Gaßner)

Real Computation and BSS Complexity

19 - 22 July 2010 Greifswald

Monday, July 19, 2010

10.00 am, R114 (Jahnstr.)

Einführende Vorträge und Diskussionen / Introduction

Arno Pauly: Weihrauch-Reduzierbarkeit und Metamathematik. Slides.

Carsten Rösnick: Komplexitätsbetrachtungen. Slides.

Christine Gaßner: Additive BSS-Maschinen. Slides.

Tuesday, July 20, 2010

10.00 am, R114 (Jahnstr.)

Tobias Gärtner and Martin Ziegler: "Real Analytic Machines and Degrees"

We study and compare in two degree-theoretic ways (iterated Halting oracles analogous to Kleene's arithmetical hierarchy and the Borel hierarchy ofdescriptive set theory) the capabilities and limitations of three models of analytic computation: BSS machines (aka real-RAM) and strongly/weakly analytic machines as introduced by Hotz et. al. (1995). Slides.

2.00 pm, Colloquium, R114 (Jahnstr.)

Russell Miller: "Factoring Polynomials and Finding Roots"

This talk will present a comparison, followed by a meta-comparison. First, within the framework of Turing computation, we discuss recent work by the speaker and others, addressing the relative difficulty of factoring polynomials and finding their roots in Turing-computable fields. (One of these problems turns out to be harder than the other, although the two are Turing-equivalent.) Then we turn to a comparison of Turing computation and BSS computation, considering the same questions for the field of real numbers and examining why the methods from the first part of the talk are no longer as relevant to these questions. Slides.

Wednesday, July 21, 2010

10.00 am, R114 (Jahnstr.)

Arno Pauly: "BSS and analytic machines in the Weihrauch-lattice"

Placing the computational power of BSS and analytic machines in the Weihrauch-lattice amounts to viewing them through the lens of TTE and allows the application of techniques recently developed to study Weihrauch-degrees. Fine-grained results on topological complexity are obtained via relativization. As a consequence, separation results regarding BSS-reductions can be classified as of topological or of algebraic nature; and new topological separations can be provided.

1.45 pm

Excursion to Zinnowitz (Usedom)

Thursday, July 22, 2010

10.00 am, R114 (Jahnstr.)

Christine Gaßner: "Degrees of Unsolvability for Additive BSS Machines"

For additive BSS machines without real constants, Klaus Meer and Martin Ziegler posed the question whether there are degrees of unsolvability which are lower than the degree of the Halting Problem and higher than one of the set of rational numbers. Inspired by this question we want to discuss several techniques in order to provide problems below the Halting Problem. Slides. More: Preprint 3/2010.