Proceedings

• S. Fischer, E. Maehle, R. Reischuk:
  Informatik 2009 - Im Fokus das Leben.
  Volume 154 of Lecture Notes in Informatics, Gesellschaft für Informatik, 2009.
  Go to website
• A. Bernstein, T. Dreier, S. Hölldobler, G. Hotz, K.-P. Löhr, P. Moltor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Sörrle, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2008.
  Volume 9 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2009.
  Go to website

Journal articles

• Wolfgang Bein, Lawrence L. Larmore, Rüdiger Reischuk:
  Knowledge States for the Caching Problem in Shared Memory Multiprocessor Systems.
  International Journal of Foundations of Computer Science, 20(1):167-184, 2009.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
  Improving the Average Delay of Sorting.
  Theoretical Computer Science, 410(11):1030-1041, 2009.
  Go to website
• Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
  Privacy in Non-Private Environments.
  Theory of Computing Systems, 2009.
  Go to website
• Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
  On the complexity of SNP block partitioning under the perfect phylogeny model.
  Discrete Mathematics, 309(18):5610-5617, 2009.
  Go to website | Show abstract
  
  ecent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genome-wide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for large-scale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkage-disequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of non-contiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is NP-hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.
• Christian Hundt, Maciej Liskiewicz, Ragnar Nevries:
  A Combinatorial Geometric Approach to Two-dimensional Robustly Pattern Matching with Scaling and Rotation.
  Theoretical Computer Science, 51(410):5317-5333, 2009.
  Go to website
• Johannes Textor, Björn Hansen:
  Hybrid Simulation Algorithms for an Agent Based Model of the Immune Response.
  Cybernetics and Systems, 40(5):390-417, 2009.
  Go to website | Show PDF | Show abstract
  
  The immune system is of central interest for the life sciences, but its high complexity makes it a challenging system to study. Computational models of the immune system can help to improve our understanding of its fundamental principles. In this paper, we analyze and extend the Celada-Seiden model, a simple and elegant agent-based model of the entire immune response, which, however, lacks biophysically sound simulation methodology. We extend the stochastic model to a stochastic-deterministic hybrid, and link the deterministic version to continuous physical and chemical laws. This gives precise meanings to all simulation processes, and helps to increase performance. To demonstrate an application for the model, we implement and study two different hypotheses about T cell-mediated immune memory.

Conference papers

• Michael Elberfeld, Johannes Textor:
  Efficient Algorithms for String-Based Negative Selection.
  In Proceedings of the 8th International Conference on Artificial Immune Systems (ICARIS 2009), Volume 5666 of Lecture Notes in Computer Science, pp. 109-121. Springer, 2009.
  Show PDF | Go to website | Show abstract
  
  String-based negative selection is an immune-inspired classification scheme: Given a self-set S of strings, generate a set D of detectors that do not match any element of S. Then, use these detectors to partition a monitor set M into self and non-self elements. Implementations of this scheme are often impractical because they need exponential time in the size of S to construct D. Here, we consider r-chunk and r-contiguous detectors, two common implementations that suffer from this problem, and show that compressed representations of D are constructible in polynomial time for any given S and r. Since these representations can themselves be used to classify the elements in M, the worst-case running time of r-chunk and r-contiguous detector based negative selection is reduced from exponential to polynomial.
• Michael Elberfeld, Ilka Schnoor, Till Tantau:
  Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
  In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), Volume 5532 of Lecture Notes in Computer Science, pp. 201-210. Springer, 2009.
  Show PDF | Go to website | Show abstract
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes from genotype data. One fast haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing as is often the case in laboratory data, the resulting incomplete perfect phylogeny haplotyping problem IPPH is NP-complete and no theoretical results are known concerning its approximability, fixed-parameter tractability, or exact algorithms for it. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP-complete; but here a fixed-parameter algorithm is known. We show that such drastic and ad hoc simplifications are not necessary to make IPPH fixed-parameter tractable: We present the first theoretical analysis of an algorithm, which we develop in the course of the paper, that works for arbitrary instances of IPPH. On the negative side we show that restricting the topology of perfect phylogenies does not always reduce the computational complexity: while the incomplete directed perfect phylogeny problem is well-known to be solvable in polynomial time, we show that the same problem restricted to path topologies is NP-complete.
• Markus Hinkelmann, Andreas Jakoby, Nina Moebius, Tiark Rompf, Peer Stechert:
  A Cryptographically t-Private Auction System.
  In Proceedings of Network and System Security 2009 (NSS 2009), pp. 44-51. IEEE Computer Society, 2009.
  Go to website | Show abstract
  
  We present a feasible cryptographically t-private protocol for electronic auctions. Our construction is based on Yao's garbled circuits and pseudorandom number generators (PRNG). Our protocol involves a field of (t+1)^2 parties for the generation of the garbled circuit and permits an arbitrary large number of bidders. The computational requirements are low: Only t+1 parties of the field have to use the PRNG, the remaining parties execute simple primitives (XOR, permuting and sharing). Independently from each other, the bidders have to stay active for one round of communication. Furthermore, each bidder has to compute t+1 XOR-operations, only. We present an implementation and evaluate its performance. The observed running time of our protocol is linear in the size of the auction circuit and the number of bidders and, as expected, grows quadratically in the parameter t.
• Markus Hinkelmann, Andreas Jakoby:
  Preserving Privacy versus Data Retention.
  In 6th International Conference on Theory and Applications of Models of Computation (TAMC 2009), Volume 5532 of Lecture Notes in Computer Science, pp. 251-260. Springer, 2009.
  Go to website | Show abstract
  
  The retention of communication data has recently attracted much public interest, mostly because of the possibility of its misuse. In this paper, we present protocols that address the privacy concerns of the communication partners. Our data retention protocols store streams of encrypted data items, some of which may be flagged as critical (representing misbehavior). The frequent occurrence of critical data items justifies the self-decryption of all recently stored data items, critical or not. Our first protocol allows the party gathering the retained data to decrypt all data items collected within, say, the last half year whenever the number of critical data items reaches some threshold within, say, the last month. The protocol ensures that the senders of data remain anonymous but may reveal that different critical data items came from the same sender. Our second, computationally more complex scheme obscures this affiliation of critical data with high probability.
• Christian Hundt, Maciej Liskiewicz:
  New Complexity Bounds for Image Matching under Rotation and Scaling.
  In Proceedings of Symposium on Combinatorial Pattern Matching (CPM), Volume 5577 of Lecture Notes in Computer Science, pp. 127-141. Springer, 2009.
  Go to website
• Johannes Textor, Benjamin Feldner:
  An XML Pipeline Based System Architecture for Managing Bibliographic Metadata.
  In Metadata and Semantics Research (MTSR'09), Volume 46 of Communications in Computer and Information Science, pp. 130-140. Springer, 2009.
  Show PDF | Go to website | Show abstract
  
  In our knowledge-based society, bibliographic metadata is everywhere. Although several metadata standards for bibliographic information have been developed and established by the professional librarian community, home-grown ad-hoc solutions are still widespread in small to medium-sized institutions. This paper presents a framework for storing, indexing, and browsing bibliographic metadata that is designed to lower the barrier for metadata standard adoption by facilitating legacy data import and integration into existing infrastructure. These goals are achieved using XML pipelines as a central design paradigm. As a practical use case, we discuss the implementation of the described architecture at a research institute in our university, where it is now in productive use for managing publication lists and the local library.

Technical reports

• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-Box Steganography.
  Technical report SIIM-TR-A-09-03, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2009.
  Show PDF | Show abstract
  
  In Steganography secret messages are encoded into unsuspicious covertexts such that an adversary cannot distinguish the resulting stegotexts from original covertexts. To accomplish their respective tasks, encoder and adversary need information about the covertext distribution. In previous analyses, the knowledge about the covertext channel was unbalanced: while the adversary had full knowledge, the encoder could only query a black-box sampling oracle. In such a situation, the only general steganographic method known is rejection sampling, for which the sampling complexity has been shown to be exponential in the message length. To overcome this somewhat unrealistic scenario and to get finer-grained security analyses, we propose a new model, called grey-box steganography. Here, the encoder starts with at least some partial knowledge about the type of covertext channel. Using the sampling oracle, he first uses machine learning techniques to learn the covertext distribution and then tries to actively construct a suitable stegotext – either by modifying a covertext or by creating a new one. The efficiency of grey-box steganography depends on the learning complexity of the concept class for the covertext channel, the efficiency of membership tests, and the complexity of the modification procedure. We will give examples showing that this finer-grained distinction provides more insight and helps constructing efficient stegosystems that are provably secure against chosen hiddentext attacks. This way we can also easily model semantic steganography.
• Michael Elberfeld:
  Perfect Phylogeny Haplotyping is Complete for Logspace.
  Technical report abs/0905.0602 [cs.CC], Computing Research Repository (CoRR), 2009.
  Go to website | Show abstract
  
  Haplotyping is the bioinformatics problem of predicting likely haplotypes based on given genotypes. It can be approached using Gusfield's perfect phylogeny haplotyping (PPH) method for which polynomial and linear time algorithms exist. These algorithm use sophisticated data structures or do a stepwise transformation of the genotype data into haplotype data and, therefore, need a linear amount of space. We are interested in the exact computational complexity of PPH and show that it can be solved space-efficiently by an algorithm that needs only a logarithmic amount of space. Together with the recently proved L-hardness of PPH, we establish L-completeness. Our algorithm relies on a new characterization for PPH in terms of bipartite graphs, which can be used both to decide and construct perfect phylogenies for genotypes efficiently.

Masters theses

• Jana Abraham:
  Konzeption und Implementation eines Frameworks zur explorativen Vermittlung von Algorithmen in der Lehre.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009, Diplomarbeit.
  Supervised by: Till Tantau, Michael Herczeg.

Bachelors theses

• S. F.:
  Approximistisches String-Matching.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Rüdiger Reischuk, Till Tantau.
• M. P.:
  Das k-Server Problem in zweidimensionalen Gittern.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Rüdiger Reischuk, Maciej Liskiewicz.
• M. P.:
  Evolution vielfaltserzeugender Mechanismen im Immunsystem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Till Tantau, Steffen Möller.
  Show PDF
• J. P.:
  Porting the Thunar File Manager to the Extensible Asynchronous Virtual File System Layer GIO.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Till Tantau.
• C. P.:
  Vertex Cover: Performance Improvement through Evolutionary Algorithms and Kernelization.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Rüdiger Reischuk.
• C. S.:
  Evolutionäre Algorithmen auf Graphen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Rüdiger Reischuk, Andreas Jakoby.
• L. S.:
  Validierung der Perfekte-Phylogenie-Annahme für die Haplotypisierung.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Till Tantau, Steffen Möller.
• B. T.:
  Systembiologische Modellierung des HIF-Regelkreises unter Normoxie und Hypoxie.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2009.
  Supervised by: Till Tantau, Jan Rupp.
  Show abstract
  
  An der Universität zu Lübeck beschäftigen sich viele Arbeitsgruppen mit dem Thema HIF. Aus diesem Grund wird ein Computerprogramm benötigt, das metabolische Systeme implementieren und simulieren kann. Die zu diesem Thema bereits existierenden Softwarelösungen sind zu komplex und zumeist nicht frei verfügbar. Daher wurde im Rahmen dieser Arbeit ein Programm entwickelt, das genau auf diesen Zweck zugeschnitten ist. Damit ist es möglich Stoffwechsel-Kreisläufe zu simulieren und die Ergebnisse direkt mit experimentellen Daten zu vergleichen. Um das Programm auf den HIF-Regelkreis anzuwenden wurde ein Modell erstellt, das die sauerstoffabhängige Akkumulation von HIF-1? in der Zelle darstellt. Das Modell wurde simuliert und die Ergebnisse mit experimentellen Daten verglichen.