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.)


Vorträge im
SS 2014

22. April 2014 und
29. April 2014
Klaus Ambos-Spies, Universität Heidelberg
Admissible ubT-Reducibilities of Finite Rank

6. Mai 2014
Sebastian Scholz, Universität Heidelberg
Präsentation Bachelorarbeit "Über die Truth-Table-Grade einfacher Mengen"

8. Mai 2014
Lutz H. Strüngmann, Hochschule Mannheim
Binary Dichotomic Algorithms and Circular Codes in Biology

15. Mai 2014
Frank Stephan, University of Singapore
Semiautomatic Structures

27. Mai 2014
Christopher Porter, Universität Paris
The invariant degrees, randomness, and semi-measures

15. Juli 2014 und
22. Juli 2014
Abdelhamid Barjane, Universität Heidelberg
An alternative combinatorial proof of the PCP theorem

28. Juli 2014
Xizhong Zheng, Arcadia University, Glenside, PA, USA
On the Computable Curves

22. April
29. April

Admissible ubT-Reducibilities 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 ubT-reducibilities 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 primitive-recursively 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 ubT-reducibility 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 ubT-reducibilities of rank 1, in the second talk we discuss admissible ubT-reducibilities of all finite ranks.

6. Mai

Über die Truth-Table-Grade 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 semi-measures

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 semi-measures, 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
22. 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 3-SAT. Given a Boolean formula in 3-CNF 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 "NP-proof" 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 polynomial-time 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 amplificattion-2007]. 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 2-variable 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 one-dimensional compact subsets of points. For simple curves of finite lengths, parametrizations can be further required to be injective or even length-normalized. 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 point-separable 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 point-separable from the other four classes of computable curves.