50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Announcements 2011


  • Hundertjahrfeier zum Leben und zur Arbeit von Alan Turing.



    • Wir gratulieren ganz herzlich Johannes Textor zum Dr. rer.nat.





      ... ein Antikörper ist ein Antikörper ist ein Antikörper und Solidarität mit Griechenland...







    • Wir gratulieren ganz herzlich Christian Hundt zum Dr. rer.nat.



    • We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to much wider class of dense fragile minimization and ranking problems including the Nearest Codeword Problem (NCP), Unique Games Problem, constrained form of matrix rigidity, correlation clustering with a fixed number of clusters, and the Betweenness Problem in tournaments.

      As a side effect of our method we obtain also the first   optimal under the ETH (exponential time hypothesis) deterministic subexponential algorithm for the weighted FAST (feedback arc set tournament) problem.

      Our results depend on a new technique of dealing with small objective functions values of minimization problemsand could be of independent interest. (Joint work with W. Schudy)

      Marek Karpinski ist auch Professor an der Bonner Internationalen Graduiertenschule für Mathematik und ein Gründungsmitglied des Hausdorff Centers für Mathematik

    • Wir gratulieren ganz herzlich Ulrich Wölfel zum Dr. rer.nat.






    • Security proofs are an essential part in modern cryptography. Often the challenge is not to come up with appropriate schemes but rather to technically prove that these schemes satisfy certain security properties. We consider cryptographic hash function constructions of output length 2n which use two calls to a blockcipher of blocklength n (so called double call double length (DC-DL-) hash functions). These constructions are motivated by the fact that due to the birthday paradoxon, the critical output length of a cryptographically secure hash function has to be twice than the blocksize of a cryptographically secure block cipher. We present for the first time techniques for proving nearly optimal lower bounds of order Omega(2^{2n}) for the preimage resistance of DC-DL- hash functions. These are the first results in this context breaking the birthday bound of O(2^n).

    • Wir gratulieren ganz herzlich Markus Hinkelmann zum Dr. rer.nat.