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.)
24. April 2017 02. Mai 2017 09. Mai 2017 30. Mai 2017 6. Juni 2017 13. Juni 2017 14. Juni 2017 20. Juni 2017 27. Juni 2017 27. Juni 2017 31. Juli 2017 1. August 2017 2. August 2017 3. August 2017 14. August 2017
 
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 n^{m/3+O(1)} and n^{O(√ n))}. The talk will present an improved quasipolynomial algorithm with runtime O(n^{log(m)+8}) which determines the winner and the winning strategy. Furthermore, if m < log(n), one can determine the winner in time O(n^{5}); thus the problem is fixedparameter 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 BlumShubSmale machines for computability in analysis.
We continue the study of the computational strength of infinite time BlumShubSmale machines (ITBM) performing computations over the reals in ordinal time started by P. Koepke and B. Seyfferth. We give a characterization of ITBMcomputable 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:R^{n}>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 R^{n}. We have shown that a polynomial time version of that result holds. Specifically, every polynomial time computable Lipschitz function f is differentiable at prandom elements of R^{n}. 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 prandomness. The other one is the notion of pporosity. Porosity is an important notion of smallness of sets in metric spaces. Porous sets appear naturally in contexts related to differentiability and Lipschitzlike regularity. We define a polytime 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 prandomness in R^{n}.

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 timebounded Kolmogorov complexity.
