50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Publications 2006


  • R. Reischuk
    Privacy-Preserving Information Processing - Complexity Issues to Establish Security
    Economic Globalization and the Choice of Asia - Collection of the Papers of Shanghai Forum 2005, W. Shenghon, J. Kim (Ed.) Fudan University Shanghai, 2006, 122-136
  • J. Gramm, T. Hartman, T. Nierhoff, R. Sharan, T. Tantau
    On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model
    Proc. of the 6th. Workshop on Algorithms in Bioinformatics (WABI 2006), LNCS 4175, Springer Verlag 2006, 92 - 102
  • J. Arpe, R. Reischuk
    Learning Juntas in the Presence of Noise
    Proc. of the 3rd International Conference on Theory and Applications of Models of Computation (TAMC 2006), LNCS 3959, Springer-Verlag 2006, 387-398
  • J. Arpe, R. Reischuk
    On the Complexity of Grammar-Based Compression
    Proc. of the IEEE Data Compression Conference (DCC 2006), IEEE Press 2006, 173-182
  • Dagstuhl Seminar Proceedings 06111 "Complexity of Boolean Functions", M. Krause, P. Pudlák, R. Reischuk, D. v. Melkebeek (Eds.), online available
  • C. Hundt, M. Liskiewicz, U. Wölfel
    Provably Secure Steganography and the Complexity of Sampling
    Proc. 17th International Symposium on Algorithms and Computation (ISAAC 2006), LNCS 4288, Springer-Verlag 2006, 754-763.
  • M. Liskiewicz
    Multiparty Computations in Non-Private Environments
    Information Transfer and Combinatorics, R. Ahlswede et al. (Eds.), LNCS 4123, Springer-Verlag 2006, 1082-1084
  • B. Manthey
    Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
    Fedor V. Fomin, Ed., Proc. of the 32rd Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science 4271, Springer-Verlag 2006, 336-347
  • J. Arpe, B. Manthey
    Approximability of Minimum AND-Circuits
    Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science 4059, Springer-Verlag 2006, 292-303
  • F. J. Balbach, T. Zeugmann
    Teaching Memoryless Randomized Learners Without Feedback
    Proc. of the17th International Conference, ALT 2006 (Algorithmic Learning Theory), Lecture Notes in Artificial Intelligence 4264, Springer Verlag 2006, 93-108
  • F. J. Balbach, T. Zeugmann
    Teaching Randomized Learners
    Proceedings of the 19th Annual Conference on Learning Theory (COLT 2006), Lecture Notes in Artificial Science 4005, Springer-Verlag 2006, 229–243
  • D. Varacca, H. Völzer
    Temporal logics and model checking for fairly correct systems
    Proceedings LICS 2006, (21st Symposium on Logic in Computer Science), IEEE Press, Aug 2006, 389-398
  • B. Manthey
    On Approximating Restricted Cycle Covers
    Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), Lecture Notes in Computer Science 3879, Springer-Verlag 2006, 282-295


  • M. Bläser, B. Manthey, J. Sgall
    An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality
    Journal of Discrete Algorithms, 4(4), 2006, 623-632
  • D. Varacca, H. Völzer. G. Winskel
    Probabilistic Event Structures and Domains
    Theoretical Computer Science, 358, 2006, 173-199
  • J. Case, S. Jain, R. Reischuk, T. Zeugmann
    Learning a Subclass of Regular Patterns in Polynomial Time
    Theoretical Computer Science 364, 2006, 115-131
  • A. Jakoby, M. Liskiewicz, R. Reischuk
    Space Efficient Algorithms for Directed Series-parallel Graphs
    Journal of Algorithms, Vol. 60 (2), 2006, 85-114
  • M. Bläser, A. Jakoby, M. Liskiewicz, B. Manthey
    Private Computation - k-connected versus 1-connected Networks
    Journal of Cryptology, Vol. 19 (3), July 2006, 341-357
  • F. C. Freiling, H. Völzer
    Illustrating the impossibility of crash-tolerant consensus in asynchronous systems
    ACM SIGOPS Operating Systems Review, Vol. 40, No. 2, ACM Press, April 2006, 105-109
  • J.Gramm, T. Nierhoff, R. Sharan, T. Tantau
    Haplotyping with Missing Data via Perfect Path Phylogenies
    Discrete and Applied Mathematics, 2006, to appear
  • B. Manthey, R. Reischuk
    Smoothed Analysis of Binary Search Trees
    Theoretical Computer Science, to appear
  • D. Varacca, H. Völzer
    New Perspectives on Fairness
    Bulletin of the EATCS, Vol. 90, Oct 2006, pp. 90-108

Monografien, Editorium, Buchbeiträge

  • A. Bernstein, T. Dreier, S. Hölldobler, K. Löhr, P. Molitor, G. Neumann, R. Reischuk, S. Saupe, M. Spiliopoulou, Dr. Wagner (Ed.)
    Ausgezeichnete Informatikdissertationen 2005
    Lecture Notes in Informatics D6, Gesellschaft für Informatik 2006
  • R. Karp, T. Nierhoff, T. Tantau
    Optimal Flow Distribution Among Multiple Channels with Unknown Capacities
    Essays in Theoretical Computer Science in Memory of Shimon Even. O. Reingold, A. L. Rosenberg, A. L. Selman (Ed.). Volume 3895 of Festschriften, Springer-Verlag 2006, 111 - 128
  • M. Bläser, P. Krysta, R. Reischuk, B. Vöcking (Ed.)
    Algorithmic Game Theory
    LNCS 2006 to appear
  • N. Cesa-Bianchi, R. Reischuk, T. Zeugmann (Ed.)
    Algorithmic Learning Theory (ALT'02)
    Theorectical Computer Science 350, No. 1, Special Issue 2006


  • T. Tantau
    The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters
    Technical Report TR06-035, Electronic Colloquium on Computational Complexity, eccc.hpi-web.de/eccc, 2006. Abstract
  • A. Jakoby, M. Liskiewicz, and A. Madry
    Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment
    Technical Report quant-ph/0605150, Quantum Physics e-Print Archive, 2006
  • F.J. Balbach, T. Zeugmann
    On the Teachability of Randomized Learners
    TCS Technical Report TCS-TR-A-06-13, Division of Computer Science, Report Series A, Hokkaido University, Graduate School of Information Science and Technology, April 26, 2006