Editorium

• A. Bernstein, W. Effelsberg, F. Freiling, S. Hölldobler, H.-P. Lenhof, P. Molitor, G. Neumann, R. Reischuk, N. Schweikardt, M. Spiliopoulou, H. Störrle, S. Süsstrunk:
  Ausgezeichnete Informatikdissertationen 2014.
  Band 165 von Lecture Notes in Informatics, Dissertationen, GI, 2015.

Zeitschriftenartikel

• Michael Elberfeld, Christoph Stockhusen, Till Tantau:
  On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
  Algorithmica, 71(3):661-701, 2015.
  Website anzeigen | Zusammenfassung anzeigen
  
  The parameterized complexity of a problem is generally considered ``settled'' once it has been shown to be fixed-parameter tractable or to be complete for a class in a parameterized hierarchy such as the weft hierarchy. Several natural parameterized problems have, however, resisted such a classification. In the present paper we argue that, %at least in some cases, this is due to the fact that the parameterized complexity of these problems can be better understood in terms of their \emph{parameterized space} or \emph{parameterized circuit} complexity. This includes well-studied, natural problems like the feedback vertex set problem, the associative generability problem, or the longest common subsequence problem. We show that these problems lie in and may even be complete for different parameterized space classes, leading to new insights into the problems' complexity. The classes we study are defined in terms of different forms of bounded nondeterminism and simultaneous time--space bounds.
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Security Levels in Steganography - Insecurity does not Imply Detectability.
  Electronic Colloquium on Computational Complexity (ECCC), 22(10)2015.
  Website anzeigen | Zusammenfassung anzeigen
  
  This paper takes a fresh look at security notions for steganography -- the art of encoding secret messages into unsuspicious covertexts such that an adversary cannot distinguish the resulting stegotexts from original covertexts. Stegosystems that fulfill the security notion used so far, however, are quite inefficient. This setting is not able to quantify the power of the adversary and thus leads to extremely high requirements. We will show that there exist stegosystems that are not secure with respect to the measure considered so far, still cannot be detected by the adversary in practice. This indicates that a different notion of security is needed which we call \emph{undetectability}. We propose different variants of (un)-detectability and discuss their appropriateness. By constructing concrete examples of stegosystems and covertext distributions it is shown that among these measures only one manages to clearly and correctly differentiate different levels of security when compared to an intuitive understanding in real life situations. We have termed this \emph{detectability on average}. As main technical contribution we design a framework for steganography that exploits the difficulty to learn the covertext distribution. This way, for the first time a tight analytical relationship between the task of discovering the use of stegosystems and the task of differentiating between possible covertext distributions is obtained.

Konferenzbeiträge

• Max Bannach, Christoph Stockhusen, Till Tantau:
  Fast Parallel Fixed-Parameter Algorithms via Color Coding.
  In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs, 2015.
  Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  
  Fixed-parameter algorithms have been successfully applied to solve numerous difficult problems within acceptable time bounds on large inputs. However, most fixed-parameter algorithms are inherently \emph{sequential} and, thus, make no use of the parallel hardware present in modern computers. We show that parallel fixed-parameter algorithms do not only exist for numerous parameterized problems from the literature -- including vertex cover, packing problems, cluster editing, cutting vertices, finding embeddings, or finding matchings -- but that there are parallel algorithms working in \emph{constant} time or at least in time \emph{depending only on the parameter} (and not on the size of the input) for these problems. Phrased in terms of complexity classes, we place numerous natural parameterized problems in parameterized versions of AC$^0$. On a more technical level, we show how the \emph{color coding} method can be implemented in constant time and apply it to embedding problems for graphs of bounded tree-width or tree-depth and to model checking first-order formulas in graphs of bounded degree.
• Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein:
  Fully Dynamic Bin Packing Revisited.
  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Band 40 von Leibniz International Proceedings in Informatics (LIPIcs), S. 135-151. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
  Website anzeigen | Zusammenfassung anzeigen
  
  We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + epsilon for the number of bins, a relatively simple argument proves a lower bound of Omega(1/epsilon) of the migration factor. We establish a fairly close upper bound of O(1/epsilon^4 log(1/epsilon)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1/epsilon. The previous best trade-off was for an asymptotic competitive ratio of 5/4 for the bins (rather than 1+epsilon) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized).
• Matthias Ernst, Maciej Liskiewicz, Rüdiger Reischuk:
  Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples.
  In Proc. International Symposium on Algorithms and Computation (ISAAC 2015), Band 9472 von Lecture Notes in Computer Science, S. 151-162. Springer, 2015.
  Website anzeigen | Zusammenfassung anzeigen
  
  Proper learning from positive samples is a basic ingredient for designing secure steganographic systems for unknown covertext channels. In addition, security requirements imply that the hypothesis should not contain false positives. We present such a learner for k-term DNF formulas for the uniform distribution and a generalization to q-bounded distributions. We briefly also describe how these results can be used to design a secure stegosystem.
• Till Tantau:
  Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.
  In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Band 30 von Leibniz International Proceedings in Informatics (LIPIcs), S. 703-715. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
  Website anzeigen | Zusammenfassung anzeigen
  
  Descriptive complexity theory aims at inferring a problem's computational complexity from the syntactic complexity of its description. A cornerstone of this theory is Fagin's Theorem, by which a property is expressible in existential second-order logic (ESO logic) if, and only if, it is in NP. A natural question, from the theory's point of view, is which syntactic fragments of ESO logic also still characterize NP. Research on this question has culminated in a dichotomy result by Gottlob, Kolaitis, and Schwentick: for each possible quantifier prefix of an ESO formula, the resulting prefix class over graphs either contains an NP-complete problem or is contained in P. However, the exact complexity of the prefix classes inside P remained elusive. In the present paper, we clear up the picture by showing that for each prefix class of ESO logic, its reduction closure under first-order reductions is either FO, L, NL, or NP. For undirected self-loop-free graphs two containment results are especially challenging to prove: containment in L for the prefix \exists R_1\cdots \exists R_n \forall x \exists y and containment in FO for the prefix \exists M \forall x \exists y for monadic M. The complex argument by Gottlob et al. concerning polynomial time needs to be carefully reexamined and either combined with the logspace version of Courcelle's Theorem or directly improved to first-order computations. A different challenge is posed by formulas with the prefix \exists M \forall x\forall y, which we show to express special constraint satisfaction problems that lie in L.
• Johannes Textor, Alexander Idelberger, Maciej Liskiewicz:
  On the Faithful DAGs of a Dependency Graph.
  In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI'15), S. 882-891. AUAI Press, 2015.
  PDF anzeigen
• Benito van der Zander, Johannes Textor, Maciej Liskiewicz:
  Efficiently Finding Conditional Instruments for Causal Inference.
  In IJCAI 2015, Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, July 25-31, 2015, S. 3243-3249. AAAI Press / International Joint Conferences on Artificial Intelligence, 2015.
  PDF anzeigen

Master- und Diplomarbeiten

• A. I.:
  Algorithmische Fragestellungen in der Kausalitätstheorie.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Maciej Liskiewicz, Rüdiger Reischuk.
• F. K.:
  Efficient Estimation of Evolutionary Distances.
  Max-Planck-Institut für Evolutionsbiologie, Plön, 2015.
  Gutachter: Bernhard Haubold, Till Tantau.
• T. M.:
  Runetime Verification Logics for Object-Oriented Real-Time Systems.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2015.
  Gutachter: Martin Leucker, Till Tantau.
• T. S.:
  Schwere Instanzen für NP-schwere Probleme.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Rüdiger Reischuk, Ralf Möller.
• F. T.:
  Construction of Two-Layer Transportation Networks.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Rüdiger Reischuk, Maciej Liskiewicz.
• J. T.:
  Minimierung symbolischer nichtdeterministischer Büchi-Automaten.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2015.
  Gutachter: Martin Leucker, Till Tantau.

Bachelor- und Studienarbeiten

• K.-D. B.:
  Graph-basierte Wasserzeichen für Software.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Maciej Liskiewicz, Martin Leucker.
• A. D.:
  Entwurf und Implementierung von Routing-Algorithmen in TikZ.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Till Tantau, Martin Teichert.
• M. D.:
  Genetische Algorithmen für das Minimum Dominating Set-Problem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Rüdiger Reischuk, Karsten Keller.
• Z. H.:
  Development and Examination of a Huffman-coding based Stegosystem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Maciej Liskiewicz, Rüdiger Reischuk.
• M.-L. K.:
  An Extension of TikZ for Automated Pedigree Construction.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Till Tantau, Amir Madany Mamlouk.
• M. K.:
  From 2-Ways Nondeterministic Büchi Automata to Alternating Büchi Automata.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2015.
  Gutachter: Martin Leucker, Till Tantau.
• N. K.:
  Secure Multiparty Computations in Bitcoin.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Maciej Liskiewicz, Stefan Fischer.
• T. L.:
  Implementation of a Simplex-Based Isosurfacing Method for Medical Image Data.
  Universität zu Lübeck, Institut für Medizinische Informatik, 2015.
  Gutachter: Jan Ehrhardt, Maciej Liskiewicz.
• A. A. L.:
  Probabilistische Analyse und Minimierung von Flussnetzwerken.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Rüdiger Reischuk, Martin Teichert.
• J. O.:
  Untere Schranken für Online-Bin-Packing-Modelle.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Till Tantau, Stefan Fischer.
• J. C. P.:
  Algorithmisches Zeichnen von RNA-Hairpin-Strukturen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Till Tantau, Amir Madany Mamlouk.
• C. P.:
  An Algorithmic Toolbox to Facilitate the Genetic Finite Automata Based Approach for Negative Selection.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Maciej Liskiewicz, Martin Leucker.
• A. P.:
  Extending Freeze LTL on Multi-Attributed Data Words with Quantifiers.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2015.
  Gutachter: Martin Leucker, Till Tantau.
• L. K. S.:
  On polytopes describing multi-terminal network flows.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2015.
  Gutachter: Rüdiger Reischuk, Andreas Rößler.