Hauptseminar Mathematische Logik und Theoretische Informatik

Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in SR 1 des Gebäudes INF 205.
(The talks are usually on Tuesday at 4 p.m. in SR 1 of building INF 205.)


 

Vorträge im
SoSe 2017

24. April 2017
Rodney G. Downey, Victoria University of Wellington
Totally omega-c.a. Degrees


02. Mai 2017
Helena Karsch, Universität Heidelberg
Der Satz von Kahr-Moore-Wang


09. Mai 2017
Frank Stephan, National University of Singapore
Deciding parity games in quasipolynomial time


30. Mai 2017
Klaus Ambos-Spies, Universität Heidelberg
Multiple Permitting


6. Juni 2017
Klaus Ambos-Spies, Universität Heidelberg
Splittings of computably enumerable sets


13. Juni 2017
Andrey Morozov, Novosibirsk, Sobolev Institute of Mathematics, Russia
Infinite time Blum-Shub-Smale machines for computability in analysis


14. Juni 2017
Alex Galicki, University of Auckland, New Zealand
Feasible betting strategies and differentiability in R^n.


20. Juni 2017
Rodney G. Downey, Victoria University of Wellington
A hierarchy of degrees


27. Juni 2017
Sebastiaan Terwijn, Radboud University Nijmegen
Normalized information distance


27. Juni 2017
Sebastiaan Terwijn, Radboud University Nijmegen
Normalized information distance


31. Juli 2017
Yun Fan, Southeast University, Nanjing
On the Computable Lipschitz Degrees of the Left-C.E. Reals (1)


1. August 2017
Yun Fan, Southeast University, Nanjing
On the Computable Lipschitz Degrees of the Left-C.E. Reals (2)


2. August 2017
Yun Fan, Southeast University, Nanjing
On the Computable Lipschitz Degrees of the Left-C.E. Reals (3)


3. August 2017
Yun Fan, Southeast University, Nanjing
On the Computable Lipschitz Degrees of the Left-C.E. Reals (4)


14. August 2017
Elias Zimmermann, Universität Heidelberg
Kolmogorov Complexity and Entropy of Ergodic Sources


 



09. Mai

Deciding parity games in quasipolynomial time

 
Parity games are games on finite graphs where each node has a value. Two players, Anke and Boris, move alternately a marker through the graph and plays between the two players have infinite duration. One determines the winner of such an infinite play by taking the largest value of a node which is visited infinite often; if this value is odd then the first player Anke wins else the second player Boris wins. An important question is to determine the player who has a winning strategy in such games. One often evaluates such algorithms with respect to the run time in terms of the number n of nodes and number m of colours and other possible parameters. Prior work has given algorithms with runtime nm/3+O(1) and nO(√ n)). The talk will present an improved quasipolynomial algorithm with runtime O(nlog(m)+8) which determines the winner and the winning strategy. Furthermore, if m < log(n), one can determine the winner in time O(n5); thus the problem is fixed-parameter tractable and the algorithm brings it from the prior known complexity class XP into FPT. This is joint work of Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Li Wei and Frank Stephan.


13. Juni

Infinite time Blum-Shub-Smale machines for computability in analysis.

 
We continue the study of the computational strength of infinite time Blum-Shub-Smale machines (ITBM) performing computations over the reals in ordinal time started by P. Koepke and B. Seyfferth. We give a characterization of ITBM-computable functions via iterated Turing jump and discuss the adequacy of this approach to our intuitive imaginations of computability used in analysis. (Joint work with Peter Koepke)


14. Juni

Feasible betting strategies and differentiability in R^n

 
Rademacher's theorem states that every Lipschitz function f:Rn->R is almost everywhere differentiable. In effective setting it can be shown that every computable Lipschitz function is differentiable at all computably random elements of Rn. We have shown that a polynomial time version of that result holds. Specifically, every polynomial time computable Lipschitz function f is differentiable at p-random elements of Rn. The proof is somewhat long and technical, hence, instead of presenting the whole proof, we will describe some of the tools (which are of independent interest) that had to be developed in order to demonstrate the result. One of them is a version of one of the directions of van Lambalgen's theorem for p-randomness. The other one is the notion of p-porosity. Porosity is an important notion of smallness of sets in metric spaces. Porous sets appear naturally in contexts related to differentiability and Lipschitz-like regularity. We define a poly-time version of this notion and characterize it in terms of polynomial time computable martingales. We show how this notion can be useful for proving results about p-randomness in Rn.


27. Juni

Normalized information distance

 
Information distance was introduced by Bennett, Gacs, Li, Vitanyi, and Zurek in 1998. It is a notion based on Kolmogorov complexity, a measure of complexity from computability theory with a versatile mathematical theory. For example, Kolmogorov complexity plays a prominent role in the theory of algorithmic randomness. Information distance, and derived notions such as normalized information distance, have proven useful in a number of ways. Besides being interesting for theoretical reasons, they have led to a number of surprising practical applications, of which we will show some examples. In this talk we will discuss the complexity of normalized information distance, and related results about time-bounded Kolmogorov complexity.