Hauptseminar Mathematische Logik und Theoretische Informatik
Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in Raum 134 des Gebäudes INF 294.
(The talks are usually on Tuesday at 4 p.m. in Room 134 of building INF 294.)
22. April 2014 und 6. Mai 2014 8. Mai 2014 15. Mai 2014 27. Mai 2014 15. Juli 2014 und 28. Juli 2014  
22. April 
Admissible ubTReducibilities of Finite Rank
A uniformly computable class F of functions defines a uniformly bounded Turing (ubT, for short) reducibility where the reductions are Turing reductions which have their use bounded by some function in F. Such a reducibility is admissible if it is reflexive and transitive. Examples of admissible ubTreducibilities are identity bounded Turing (ibT) reducibility where the bound is the identity function, computable Lipschitz (cl) reducibility where the bounds are the identity plus a constant, linearly bounded Turing (lbT) reducibility where the bounds are linear, and primitiverecursively bounded Turing reducibility where the bounds are primitive recursive. Among these and other "natural" examples, ibT reducibility is the only admissible ubT reducibility which is induced by a finite class of functions, in fact by a single function. In our talks we discuss admissible ubT reducibilities induced by finite classes from a general point of view. We say that an admissible ubTreducibility r has finite rank if it is induced by a finite class F of bounds, and we say that r has rank k if k is minimal such that r is induced by a class of cardinality k. In the first talk we discuss the admissible ubTreducibilities of rank 1, in the second talk we discuss admissible ubTreducibilities of all finite ranks.

6. Mai 
Über die TruthTableGrade einfacher Mengen

8. Mai 
Binary Dichotomic Algorithms and Circular Codes in Biology

15. Mai 
Semiautomatic Structures
Semiautomatic structures generalise automatic structures in the sense
that for some of the relations and functions in the structure one only
requires the derived relations and structures are automatic when all
but one input are filled with constants. One can also
permit that this applies to equality in the structure so that only
the sets of representatives equal to a given element of the structure
are regular while equality itself is not an automatic relation on the
domain of representatives. It is shown that one can find semiautomatic
representations for the field of rationals and also for finite algebraic
field extensions of it. Furthermore, one can show that infinite algebraic
extensions of finite fields have semiautomatic representations in which
the addition and equality are both automatic. Further prominent examples
of semiautomatic structures are term algebras, any relational structure
over a countable domain with a countable signature and any permutation
algebra with a countable domain. Furthermore, examples of structures
which fail to be semiautomatic are provided.
This is joint work with Sanjay Jain, Bakhadyr Khoussainov, Dan Teng
and Siyuan Zou.

27. Mai 
The invariant degrees, randomness, and semimeasures
In computability theory, there are a number of degree structures for comparing the computational strength of a sequence or collection of sequences with respect to deterministic computation, such as the Turing degrees, the Medvedev degrees, and the Muchnik degrees. What if we considered instead the computational strength of a sequence or collection of sequences with respect to probabilistic computation?
The goal of this talk is to introduce one such degree structure, namely the invariant degrees, which were introduced by Levin and V'yugin. Roughly, an invariant degree is an equivalence class of Turing invariant collections of sequences, where two Turing invariant collections of sequences A and B are equivalent if any probabilistic algorithm that produces a member of A with positive probability p produces a member of B with probability greater than or equal to p, and vice versa.
In addition to introducing the invariant degrees, I will (1) explain the connection between the invariant degrees and algorithmic randomness, (2) discuss a technique developed by V'yugin for constructing semimeasures, which in turn can be used to define invariant degrees, and (3) highlight a new application of V'yugin's technique obtained in joint work with Rupert Hölzl.

15. Juli 
An alternative combinatorial proof of the PCP theorem
NP is the complexity class of problems for which it is easy to check that a solution is correct. Consider for example the problem 3SAT. Given a Boolean formula in 3CNF and a proposed assignment, it is trivial to check whether the assignment satisfies the formula by plugging the values into the formula. Such an assignment is an "NPproof" for the satisfiability of the formula.
An alternative way to define NP is as the class of all sets L that have efficient proof systems: proof systems in which there is a polynomialtime algorithm that verifies correctness of the statement "x in L" with assistance of a proof.
The verifier must check every single proof step/clause in order to make sure that the proof is correct.
In contrast, the PCP theorem gives each set in NP an alternative proof system, in which proofs are robust. In this system a proof for false statement is guaranteed to have so many errors that a verifier can randomly read only a few bits from the proof and decide, with high probability of success, whether the proof is valid or not. The verifier is both enhanced with additional randomness and restricted in its access (oracle access) to the proof.
The original proof and formulation of the PCP stemmed out of research on proof verification. The techniques used in the proof are largely based on algebraic encodings and testing results that are generally called "low degree testing".
More recently a combinatorial proof was given by Dinur [PCP theorem by gap amplificattion2007]. This proof is described as a hardness of aproximation result, and it relies on rapid mixing of random walks on expander graphs.
The key to constructing such a PCP is a transformation that amplifies errors in a proof via a gradual process of logarithmically many steps. It starts from a "trivial PCP system" that rejects false assertions with probability inversely proportional to their lenght, and doubles the rejection probabbility (the gap) in each step. In each step, the constant query complexity is preserved and the length of the PCP oracle is increased only by a constant factor. Thus, the process gradually transforms a very weak PCP system into a remarkable PCP system as in the PCP theorem. In order to describe the aformentioned process we need to redefine PCP systems. For technical reasons it is more convenient to describe the process as an iterated Reduction of a "constraint satisfaction" problem (CSP) to itself.
We refer to systems of 2variable constraints, wich are represented by (labeled) graphs.

28. Juli 
On the Computable Curves
In mathematics curves are typically defined as the images of continuous real functions (so called parametrizations) on a closed interval. They can also be defined as connected onedimensional compact subsets of points. For simple curves of finite lengths, parametrizations can be further required to be injective or even lengthnormalized. All of these four approaches to curves are classically equivalent. However, if we define four different versions of computable curves based on the effectivization of these four approaches. It turns out that they are all different, and hence, we get four different
classes of “computable curves”. More interestingly, these four classes are even
pointseparable in the sense that the sets of points covered by computable curves of different versions are also different. However, if we consider only computable curves of computable lengths, then all four versions of computable curves become equivalent. This shows that the definition of computable curves is robust, at least for those of computable lengths. In addition, we show that the class of computable curves of computable lengths is pointseparable from the other four classes of computable curves.
