Editorium

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

Zeitschriftenartikel

• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning Residual Alternating Automata.
  Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
  Website anzeigen | Zusammenfassung anzeigen
  
  Residuality plays an essential role for learning finite automata. While residual deterministic and nondeterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman have initiated a systematic study of residual AFAs and proposed an algorithm called AL* -an extension of the popular L* algorithm - to learn AFAs. Based on computer experiments they conjectured that AL* produces residual AFAs, but have not been able to give a proof. In this paper we disprove this conjecture by constructing a counterexample. As our main positive result we design an efficient learning algorithm, named AL**, and give a proof that it outputs residual AFAs only. In addition, we investigate the succinctness of these different FA types in more detail.
• Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Proper Learning of k-term DNF Formulas from Satisfying Assignments.
  Electronic Colloquium on Computational Complexity (ECCC), 24(114)2017.
  Website anzeigen | Zusammenfassung anzeigen
  
  In certain applications there may only be positive samples available to to learn concepts of a class of interest, and this has to be done properly, i.e. the hypothesis space has to coincide with the concept class, and without false positives, i.e. the hypothesis always has be a subset of the real concept (one-sided error). For the well studied class of k-term DNF formulas it has been known that learning is difficult. Unless RP = NP, it is not feasible to learn k-term DNF formulas properly in a distribution-free sense even if both positive and negative samples are available and even if false positives are allowed. This paper constructs an efficient algorithm that for arbitrary fixed k, if samples are drawn from distributions like uniform or q-bounded ones, properly learns the class of k-term DNFs without false positives from positive samples alone with arbitrarily small relative error.
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Security levels in steganography - Insecurity does not imply detectability.
  Theoret. Comput. Sci., (692):25-45, 2017.
  Website anzeigen

Konferenzbeiträge

• Max Bannach, Sebastian Berndt, Thorsten Ehlers:
  Jdrasil: A Modular Library for Computing Tree Decompositions.
  In International Symposium on Experimental Algorithms (SEA 2017), Band 75 von LIPIcs, S. 28:1--28:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
  Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  
  While the theoretical aspects concerning the computation of tree width - one of the most important graph parameters - are well understood, it is not clear how it can be computed practically.We present the open source Java library Jdrasil that implements several different state of the art algorithms for this task. By experimentally comparing these algorithms, we show that the default choices made in Jdrasil lead to an competitive implementation (it took the third place in the first PACE challenge) while also being easy to use and easy to extend.
• Sebastian Berndt, Maciej Liskiewicz:
  Algorithm Substitution Attacks from a Steganographic Perspective.
  In Proc. 24th ACM Conference on Computer and Communications Security (CCS 2017), S. 1649-1660. ACM Press, 2017.
  Website anzeigen | Zusammenfassung anzeigen
  
  The goal of an algorithm-substitution attack (ASA), also called a subversion attack (SA), is to replace an honest implementation of a cryptographic tool by a subverted one which allows to leak private information while generating output indistinguishable from the honest output. Bellare, Paterson, and Rogaway provided at CRYPTO '14 a formal security model to capture this kind of attacks and constructed practically implementable ASAs against a large class of symmetric encryption schemes. At CCS'15 Ateniese, Magri, and Venturi extended the model to allow the attackers to work in a fully-adaptive and continuous fashion and proposed subversion attacks against digital signature schemes. Both papers also showed impossibility of ASAs in cases when the cryptographic tools are deterministic. Also at CCS'15, Bellare, Jaeger and Kane strengthened the original model and proposed a universal ASA against sufficiently random encryption schemes. In this paper we analyze ASAs from the point of view of steganography - the well known concept of hiding the presence of secret messages in legal communications. While a close connection between ASAs and steganography is known, this lacks a rigorous treatment. We consider the common computational model for secret-key steganography and prove that successful ASAs correspond to secure stegosystems on certain channels and vice versa. This formal proof allows us to conclude that ASAs are stegosystems and to »rediscover« several results concerning ASAs known in the steganographic literature.
• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning Residual Alternating Automata.
  Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), S. 1749-1755. AAAI Press, 2017.
  Website anzeigen | Zusammenfassung anzeigen
  
  Residuality plays an essential role for learning finite automata. While residual deterministic and non-deterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman (2015) have initiated a systematic study of residual AFAs and proposed an algorithm called AL* – an extension of the popular L* algorithm – to learn AFAs. Based on computer experiments they have conjectured that AL* produces residual AFAs, but have not been able to give a proof. In this paper we disprove this conjecture by constructing a counterexample. As our main positive result we design an efficient learning algorithm, named AL**, and give a proof that it outputs residual AFAs only. In addition, we investigate the succinctness of these different FA types in more detail.
• Martin R. Schuster, Maciej Liskiewicz:
  New Abilities and Limitations of Spectral Graph Bisection.
  In 25th Annual European Symposium on Algorithms, (ESA) 2017, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
• Till Tantau:
  Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)..
  In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), S. 4:1--4:4. DROPS, 2017.
  Website anzeigen | Zusammenfassung anzeigen
  
  Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs are structured in a certain way, then the problem can be solved with a certain amount of resources. As an example, by Courcelle's Theorem all monadic second-order ("in a certain logic") properties of graphs of bounded tree width ("structured in a certain way") can be solved in linear time ("with a certain amount of resources"). Such theorems have become a valuable tool in algorithmics: If a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. The talk is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space classes and parallel computation, and tries to give a flavor of the range of

Technische Berichte

• Martin R. Schuster, Maciej Liskiewicz:
  New Abilities and Limitations of Spectral Graph Bisection.
  Technischer Bericht 1701.01337, arXiv, 2017.
  Website anzeigen | Zusammenfassung anzeigen
  
  Spectral based heuristics belong to well-known commonly used methods which determines provably minimal graph bisection or outputs "fail" when the optimality cannot be certified. In this paper we focus on Boppana's algorithm which belongs to one of the most prominent methods of this type. It is well known that the algorithm works well in the random \emph{planted bisection model} -- the standard class of graphs for analysis minimum bisection and relevant problems. In 2001 Feige and Kilian posed the question if Boppana's algorithm works well in the semirandom model by Blum and Spencer. In our paper we answer this question affirmatively. We show also that the algorithm achieves similar performance on graph classes which extend the semirandom model. Since the behavior of Boppana's algorithm on the semirandom graphs remained unknown, Feige and Kilian proposed a new semidefinite programming (SDP) based approach and proved that it works on this model. The relationship between the performance of the SDP based algorithm and Boppana's approach was left as an open problem. In this paper we solve the problem in a complete way by proving that the bisection algorithm of Feige and Kilian provides exactly the same results as Boppana's algorithm. As a consequence we get that Boppana's algorithm achieves the optimal threshold for exact cluster recovery in the \emph{stochastic block model}. On the other hand we prove some limitations of Boppana's approach: we show that if the density difference on the parameters of the planted bisection model is too small then the algorithm fails with high probability in the model.

Dissertationen

• Christoph Stockhusen:
  On the Space and Circuit Complexity of Parameterized Problems.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Till Tantau, Heribert Vollmer.

Master- und Diplomarbeiten

• D. H.:
  Dreiwertige Timed-LTL-Semantik.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2017.
  Gutachter: Martin Leucker, Till Tantau.
• A. A. L.:
  Möglichkeiten und Grenzen der parallelen Berechnung von Kerneln.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Till Tantau, Martin Leucker.
• A. P.:
  SMT-based Flat Model-Checking for LTL with Counting.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2017.
  Gutachter: Martin Leucker, Till Tantau.
• J. W.:
  Differential Privacy: Choosing Parameters for Multiple Studies.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Rüdiger Reischuk, Thomas Eisenbarth.

Bachelor- und Studienarbeiten

• P. D.:
  Randomisierte Algorithmen für das Färbungsproblem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Rüdiger Reischuk, Till Tantau.
• T. P.:
  Effiziente parallele Kernel-Algorithmen für das Vertex-Cover-Problem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Till Tantau, Ralf Möller.
• V. R.:
  Complexity of the Subgraph Homeomorphism Problem Parameterized by Directed Treewidth.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Till Tantau, Rüdiger Reischuk.
• L. S.:
  Algorithmische Konstruktion von Primern.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Till Tantau, Amir Madany.
• L. W.:
  Lange Wege in Gittergraphen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2017.
  Gutachter: Rüdiger Reischuk, Christian Bey.