2023

• Florian Thaeter, Rüdiger Reischuk:
  Improving Time Complexity and Utility of k-anonymous Microaggregation.
  In E-Business and Telecommunications, 18.~Int. Conference ICETE 2021, Volume 1795 of Communications in Computer and Information Science, pp. 195-223. Springer, 2023.
• S. Apel, A. Bernstein, F. Freiling, H. Lenhof, G. Neumann, R. Reischuk, K. Römer, B. Scheuermann, N. Schweikardt, K. Wehrle:
  Ausgezeichnete Informatikdissertationen 2022.
  Volume D23 of Lecture Notes in Informatics, Gesellschaft für Informatik, 2023.

2022

• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Algorithmica, 84:3459–3488, 2022.
  Go to website | Show abstract
  
  Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k d (which is a polynomial as d is a constant), and they do so in time m · 2d poly(d) for a small polynomial poly(d) (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k d kernel. This paper presents a deterministic solution with worst-case time 3d poly(d) for updating the kernel upon inserts and time 5d poly(d) for updates upon deletions. These bounds nearly match the time 2d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deter- ministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c k ) where c = d ? 1 + O(1/d) equals the best base known for the static setting.
• Sebastian Berndt, Maciej Liskiewic, Matthias Lutter, Rüdiger Reischuk:
  Learning residual alternating automata.
  Inf. Comput., 289(Part):861-878, 2022.
• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning residual alternating automata.
  Information and Computation, (289):104981, 2022.
  Go to website
• Rüdiger Reischuk:
  The Kangaroo Problem.
  Volume 898 of Theoretical Computer Science, pp. 50-58. Elsevier, 2022.
  Go to website
• Florian Thaeter, Rüdiger Reischuk:
  Hardness of k-anonymous Microaggregation.
  Volume 303 of Discrete Applied Mathematics, pp. 149-158. Elsevier, 2022.
  Go to website
• Rüdiger Reischuk, Steffen Hölldobler et al.:
  Ausgezeichnete Informatikdissertationen 2020.
  Lecture Notes in Informatics, GI-Edition, 2022.
• Rüdiger Reischuk et al.:
  Ausgezeichnete Informatikdissertationen 2021.
  Lecture Notes in Informatics, GI-Edition, 2022.

2021

• Max Bannach, Zacharias Heinrich, Till Tantau, Rüdiger Reischuk:
  Dynamic Kernels for Hitting Sets and Set Packing.
  In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Volume 214 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  Go to website | Show abstract
  
  Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k^d (which is a polynomial kernel size as d is a constant), and they do so in time m? 2^d poly(d) for a small polynomial poly(d) (which is a linear runtime as d is again a constant). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k^d hitting set kernel in memory (including moments when no size-k hitting set exists). This paper presents a deterministic solution with worst-case time 3^d poly(d) for updating the kernel upon hyperedge inserts and time 5^d poly(d) for updates upon deletions. These bounds nearly match the time 2^d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a dynamic hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c^k) where c = d - 1 + O(1/d) equals the best base known for the static setting.
• Florian Thaeter, Rüdiger Reischuk:
  Scalable k-anonymous Microaggregation: Exploiting the Tradeoff between Computational Complexity and Information Loss.
  In Proceedings of the 18th International Conference on Security and Cryptography (SECRYPT 2021), pp. 87-98. SCITEPRESS, 2021.
  Show abstract
  
  k-anonymous microaggregation is a standard technique to improve privacy of individuals whose personal data is used in microdata databases. Unlike semantic privacy requirements like differential privacy, k-anonymity allows the unrestricted publication of data, suitable for all kinds of analysis since every individual is hidden in a cluster of size at least k. Microaggregation can preserve a high level of utility, that means small information loss caused by the aggregation procedure, compared to other anonymization techniques like generalization or suppression. Minimizing the information loss in k-anonymous microaggregation is an NP-hard clustering problem for k ? 3. Even more, no efficient approximation algorithms with a nontrivial approximation ratio are known. Therefore, a bunch of heuristics have been developed to restrain high utility – all with quadratic time complexity in the size of the database at least. We improve this situation in several respects providing a tradeoff between computational effort and utility. First, a quadratic time algorithm ONA* is presented that achieves significantly better utility for standard benchmarks. Next, an almost linear time algorithm is developed that gives worse, but still acceptable utility. This is achieved by a suitable adaption of the Mondrian clustering algorithm. Finally, combining both techniques a new class MONA of parameterized algorithms is designed that deliver competitive utility for user-specified time constraints between almost linear and quadratic.
• Rüdiger Reischuk, Steffen Hölldobler et al.:
  Ausgezeichnete Informatikdissertationen 2019.
  Lecture Notes in Informatics, Dissertations, GI-Edition, 2021.

2020

• Rüdiger Reischuk, Florian Thaeter:
  Hardness of k-anonymous microaggregation.
  Discrete Applied Mathematics, 2020.
  Go to website | Show abstract
  
  "Although corrected proofs do not have all bibliographic details available yet, they can be cited using the year of online publication and the DOI as follows: author(s), article title, publication (year), DOI. Please consult the journal's reference style for the exact appearance of these elements, abbreviation of journal names, and use of punctuation."

2019

• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Technical report , Electronic Colloquium on Computational Complexity, 2019.
  Go to website | Show abstract
  
  Computing kernels for the hitting set problem (the problem of finding a size-$k$ set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with $m$ hyperedges, each of size at most~$d$, the best algorithms can compute kernels of size $O(k^d)$ in time $O(2^d m)$. In this paper we generalize the task to the \emph{dynamic} setting where hyperedges may be continuously added and deleted and we always have to keep track of a hitting set kernel (including moments when no size-$k$ hitting set exists). We present a deterministic solution, based on a novel data structure, that needs worst-case time $O^*(3^d)$ for updating the kernel upon hyperedge inserts and time~$O^*(5^d)$ for updates upon deletions -- thus nearly matching the time $O^*(2^d)$ needed by the best static algorithm per hyperedge. As a novel technical feature, our approach does not use the standard replace-sunflowers-by-their-cores methodology, but introduces a generalized concept that is actually easier to compute and that allows us to achieve a kernel size of $\sum_{i=0}^d k^i$ rather than the typical size $d!\cdot k^d$ resulting from the Sunflower Lemma. We also show that our approach extends to the dual problem of finding packings in hypergraphs (the problem of finding $k$ pairwise disjoint hyperedges), albeit with a slightly larger kernel size of $\sum_{i=0}^d d^i(k-1)^i$.
• Zacharias Heinrich, Rüdiger Reischuk:
  Improved Dynamic Kernels for Hitting-Set.
  In 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 69-72. Inproceedings, 2019.
  Show PDF
• Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Proper learning of k-term DNF formulas from satisfying assignments.
  Journal of Computer and System Sciences, 106:129-144, 2019.
  Go to website | Show abstract
  
  In certain applications there may be only positive examples available to learn concepts of a class of interest. Furthermore, learning 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 to 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 examples are available and even if false positives are allowed. This paper constructs an efficient algorithm that, for fixed but arbitrary k and q, if examples are drawn from q-bounded distributions, it properly learns the class of k-term DNFs without false positives from positive examples alone with arbitrarily small relative error.
• Rüdiger Reischuk, Steffen Höllendobler, et al.:
  Ausgezeichnete Informatikdissertationen 2018.
  Lecture Notes in Informatic Dissertation, GI-Edition, 2019.

2018

• 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 2017.
  Volume 18 of Lecture Notes in Informatics, Gesellschaft für Informatik, 2018.
• Florian Thaeter, Rüdiger Reischuk:
  Improving Anonymization Clustering.
  In SICHERHEIT 2018, pp. 69-82. Gesellschaft für Informatik e.V., 2018.
  Go to website

2017

• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning Residual Alternating Automata.
  Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
  Go to website | Show abstract
  
  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.
• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning Residual Alternating Automata.
  Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), pp. 1749-1755. AAAI Press, 2017.
  Go to website | Show abstract
  
  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.
• 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.
  Go to website | Show abstract
  
  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.
  Go to website
• 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.
  Volume 17 of Lecture Notes in Informatics, GI, 2017.

2016

• Sebastian Berndt, Rüdiger Reischuk:
  Steganography Based on Pattern Languages.
  In Language and Automata Theory and Applications, 10th International Conference LATA 2016 Prague, Czech Republic, March 14-18, 2016, Volume Volume 9618 of Lecture Notes in Computer Science (LNCS), pp. 387-399. Springer, 2016.
  Go to website | Show abstract
  
  In order to transmit secret information, such that this transmission cannot be detected, steganography needs a channel, a set of strings with some distribution that occur in an ordinary communication. The elements of such a language or concept are called coverdocuments. The question how to design secure stegosystems for natural classes of languages is investigated for pattern languages. We present a randomized modification scheme for strings of a pattern language that can reliably encode arbitrary messages and is almost undetectable.
• 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 2015.
  Volume 16 of Lecture Notes in Informatics, Dissertationen, GI, 2016.

2015

• 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), Volume 9472 of Lecture Notes in Computer Science, pp. 151-162. Springer, 2015.
  Go to website | Show abstract
  
  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.
• 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.
  Go to website | Show abstract
  
  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.
• 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.
  Volume 165 of Lecture Notes in Informatics, Dissertationen, GI, 2015.

2014

• A. Bernstein, W. Effelsberg, S. Hölldobler, H.-P. Lenhof, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, N. Schweikardt, M. Spiliopoulou, H. Störrle, S. Süsstrunk:
  Ausgezeichnete Informatikdissertationen 2013.
  Volume 14 of Lecture Notes in Informatics, Dissertationen, GI, 2014.

2013

• A. Bernstein, W. Effelsberg, S. Hölldoble, H.-P. Lenhof, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, N. Schweikardt, M. Spiliopoulou, H. Störrle, S. Süsstrunk:
  Ausgezeichnete Informatikdissertationen 2012.
  Volume 13 of Lecture Notes in Informatics, Dissertationen, GI, 2013.
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-box steganography.
  Theoretical Computer Science, (505):27-41, 2013.
  Go to website

2012

• A. Bernstein, S. Hölldobler, G. Hotz, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Störrle, D. Wagner::
  Ausgezeichnete Informatikdissertationen 2011.
  Volume D-12 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2012.

2011

• Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Chritian Scheideler, Heribert Vollmer, Dorothea Wagner (Eds.):
  Algorithms Unplugged.
  Springer Verlag, Heidelberg, 2011.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-Box Steganography.
  Volume 6648 of Lecture Notes in Computer Science, pp. 390-402. Springer Verlag, Heidelberg, in Proceedings 8. TAMC, 2011.
  Go to website
• Rüdiger Reischuk:
  One-Way Functions: Mind the Trap -- Escape Only for the Initiated.
  In Algorithms Unplugged, pp. 131-140. Springer, 2011.
  Go to website
• Rüdiger Reischuk, Markus Hinkelmann:
  One-Way Functions. Mind the Trap – Escape Only for the Initiated.
  In Algorithms Unplugged, pp. 131-139. Springer, 2011.
  Go to website
• Rüdiger Reischuk, Johannes Textor:
  Stochastic Search With Locally Clustered Targets: Learning from T Cells.
  In 10th International Conference on Artificial Immune Systems (ICARIS 2011), Volume 6825 of Lecture Notes in Computer Science, pp. 146-159. Springer, 2011.
• A. Bernstein, S. Hölldobler, G. Hotz, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Störrle, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2010.
  Volume 11 of Lecture Notes in Informatics, Dissertationen, GI, 2011.

2010

• A. Bernstein, S. Hölldobler, G. Hotz, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Störrle, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2009.
  Volume 10 of Lecture Notes in Informatics, Dissertationen, GI, 2010.

2009

• 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
• 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.
• 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

2008

• W. Bein, L. Larmore, R. Reischuk:
  Knowledge States: A Tool for Randomized Online Algorithms.
  In Proceedings of 41. HICSS Int. Conference on System Sciences, pp. 476. IEEE Computer Society, 2008.
  Go to website
• A. Bernstein, T. Dreier, S. Hölldobler, G. Hotz, K. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Störle, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2007.
  Volume D3 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2008.
• Rüdiger Reischuk, Markus Hinkelmann:
  Einweg-Funktionen: Vorsicht Falle - Rückweg nur für Eingeweihte!
  In Taschenbuch der Algorithmen, pp. 139-148. Springer, 2008.
  Show abstract
  
  Ein Beitrag über Einweg-Funktionen im Rahmen der Algorithmen der Woche während des Jahrs der Informatik 2006.
• B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner:
  Taschenbuch der Algorithmen.
  eXamen.press, Springer, 2008.
  Go to website

2007

• Jan Arpe, Rüdiger Reischuk:
  Learning Juntas in the Presence of Noise.
  Theoretical Computer Science, 1(384):2-21, 2007.
  Go to website
• Jan Arpe, Rüdiger Reischuk:
  When Does Greedy Learning of Relevant Attributes Succeed? - A Fourier-based Characterization.
  In 13th Annual International Conference, Computing and Combinatorics, COCOON 2007, Volume 4598 of Lecture Notes in Computer Science, pp. 296-306. Springer, 2007.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
  Improving the Average Delay of Sorting.
  In 4th International Conference, Theory and Applications of Models of Computation, TAMC 2007, Volume 4484 of Lecture Notes in Computer Science, pp. 330-341. Springer, 2007.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk, Guest Eds.:
  Theory of Computing Systems.
  Volume 41/2 of Theory of Computing Systems, Springer, 2007.
  Go to website
• Bodo Manthey, Rüdiger Reischuk:
  Smoothed Analysis of Binary Search Trees.
  Theoretical Computer Science, 378(3):292-315, 2007.
  Go to website | Show abstract
  
  Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity. We investigate what happens in between by analysing the smoothed height of binary search trees: Randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions. On the one hand, we prove tight lower and upper bounds of roughly @Q((1-p)@?n/p) for the expected height of binary search trees under partial permutations and partial alterations, where n is the number of elements and p is the smoothing parameter. This means that worst-case instances are rare and disappear under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse well balanced instances can become.
• Rüdiger Reischuk:
  Designing Boolean Sorting Circuits with Optimal Average Delay.
  In Oberwolfach Reports X, Mathematisches Forschungsinstitut Oberwolfach, 2007.
• A. Bernstein, T. Dreier, S. Hölldobler, G. Hotz, K. Lohr, P. Molitor, R. Reischuk, D. Saupe, M. Spiliopoulou, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2006.
  Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2007.

2006

• Jan Arpe, Rüdiger Reischuk:
  Learning Juntas in the Presence of Noise.
  In Proc. Theory and Applications of Models of Computation TAMC'2006, Volume 3959 of Lecture Notes in Computer Science, pp. 387-398. Springer, 2006.
  Go to website
• Jan Arpe, Rüdiger Reischuk:
  On the Complexity of Optimal Grammar Based Compression.
  In Proc. 16. Data Compression Conference DCC'2006, pp. 173-182. IEEE Computer Society, 2006.
  Go to website
• A. Bernstein, T. Dreier, S. Hölldobler, K. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2005.
  Volume D6 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2006.
  Go to website
• John Case, Sanjey Jain, Rüdiger Reischuk, Thomas Zeugmann:
  Learning a Subclass of Regular Patterns in Polynomial Time.
  Theoretical Computer Science, 1(364):115-131, 2006.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Directed Series-Parallel Graphs.
  Journal of Algorithms, 2(60):85-114, 2006.
  Go to website
• Matthias Krause, Pavel Pudlak, Rüdiger Reischuk, Dieter van Melkebeek:
  Complexity of Boolean Functions.
  Volume 06111 of Dagstuhl Seminar Proceedings, Schloss Dagstuhl GmbH, 2006.
  Go to website
• Rüdiger Reischuk, Markus Hinkelmann:
  Einweg-Funktionen - Vorsicht Falle - Rückweg nur für Eingeweihte!
  Algorithmus der Woche zum Informatikjahr 2006
  Go to website | Show abstract
  
  17. Algorithmus der Woche im Informatikjahr 2006

2005

• T. Dreier, O. Günther, S. Hölldobler, K. Löhr, P. Molitor, R. Reischuk, D. Saupe, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2004.
  Volume D5 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2005.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk:
  Proceedings of the 15th International Symposium On Fundamentals of Computation Theory (FCT), Lübeck 2005.
  Volume 3623 of Lecture Notes in Computer Science, Springer, 2005.
  Go to website
• Bodo Manthey, Rüdiger Reischuk:
  Smoothed Analysis of Binary Search Trees.
  Technical report SIIM-TR-A-05-17, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2005.
  Show postscript | Show abstract
  
  Binary search trees are one of the most fundamental data structures. While the worst case height of a binary search tree is linear, the average height of binary search trees under the uniform distribution is logarithmic and one of the best studied problems in average case complexity. We investigate what happens between worst and average case, namely the smoothed height of binary search trees: we randomly perturb a given (adversarial) sequence and then consider the height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions. On the one hand, we prove tight lower and upper bounds of roughly ?(?n) (in contrast to height n in the worst case and ?(log n) on average) for the expected height of binary search trees under partial permutations and partial alterations. That means worst case instances break down under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse best case instances can become.
• Bodo Manthey, Rüdiger Reischuk:
  The Intractability of Computing the Hamming Distance.
  Theoretical Computer Science, 1-3(337):331-346, 2005.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk:
  Proceedings of the 15th International Symposium On Fundamentals of Computation Theory (FCT), Lübeck 2005.
  Volume 3623 of Lecture Notes in Computer Science, Springer, 2005.

2004

• Jan Arpe, Rüdiger Reischuk:
  On the Complexity of Optimal Grammar Based Compression.
  Technical report SIIM-TR-A-04-14, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2004.
  Show postscript | Show abstract
  
  The task of grammar-based compression is to find a small context-free grammar generating exactly one given string. We investigate the relationship between grammar-based compression of strings over unbounded and bounded alphabets. Specifically, we show how to transform a grammar for a string over an unbounded alphabet into a grammar for a block coding of that string over a fixed bounded alphabet and vice versa. From these constructions, we obtain asymptotically tight relationships between the minimum grammar sizes for strings and their block codings. Finally, we exploit an improved bound of our construction for overlap-free block codings to show that a polynomial time algorithm for approximating the minimum grammar for binary strings within a factor of c yields a polynomial time algorithm for approximating the minimum grammar for strings over arbitrary alphabets within a factor of 24c+? (for arbitrary ?>0). Since the latter problem is known to be NP-hard to approximate within a factor of 8569/8568, we provide a first step towards solving the long standing open question whether minimum grammar-based compression of binary strings is NP-complete.
• H. Beilner, T. Dreier, M. Gross, O. Günther, S. Hölldobler, K. Löhr, R. Reischuk, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2003.
  Volume D4 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2004.
  Go to website
• Wolfgang Bein, Larry Larmore, Rüdiger Reischuk:
  Knowledge States for the Caching Problem in Shared Memory Multiprocessor Systems.
  In llel Architectures, Algorithms and Networks ISPAN'2004, pp. 307-312. IEEE Computer Society, 2004.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Approximating Schedules for Dynamic Graphs Efficiently.
  Journal of Discrete Algorithms, 4(2):471-500, 2004.
  Go to website

2003

• Jan Arpe, Rüdiger Reischuk:
  Robust Inference of Funtional Relations.
  In 14 Int. Conference on Algorithmic Learning Theory ALT'2003, Volume 2842 of Lecture Notes in Artificial Intelligence, pp. 99-113. Springer, 2003.
  Go to website
• Jan Arpe, Rüdiger Reischuk:
  Robust Inference of Functional Relations.
  Technical report SIIM-TR-A-03-12, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2003.
  Show postscript | Show abstract
  
  Given n Boolean input variables representing a set of attritubes, we consider Boolean functions f (i.e., binary classifications of tuples) that actually depend only on a small but unknown subset of these variables/attributes, in the following called relevant. The goal is to determine these relevant attributes given a sequence of examples - input vectors X with their classification f(X). We analyze two simple greedy strategies and prove that they are able to achieve this goal for various kinds of Boolean functions and various input distributions according to which the examples are drawn at random. This generalizes results obtained by Akutsu, Miyano, and Kuhara for the uniform distribution. The analysis also provides explicit upper bounds on the number of necessary examples. They depend on the distribution and combinatorial properties of the function to be inferred. Our second contribution is an extension of these results to a situation where the examples contain errors, that means a certain number of input bits x_i may be wrong. This is a typical situation, for example in medical research, where not all attributes can be measured reliably. We show that even in such an error-prone situation reliable inference of the relevant attributes can be performed by proving that our greedy strategies are robust even against a linear number of errors.
• H. Beilner, H. Fiedler, M. Gross, O. Günther, S. Hölldobler, G. Hotz, K. Löhr, R. Reischuk, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2002.
  Volume D3 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2003.
  Go to website
• John Case, Sanjey Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann:
  Learning a Subclass of Regular Pattern in Polynomial Time.
  In 14 Int. Conference on Algorithmic Learning Theory ALT'2003, Volume 2842 of Lecture Notes in Artificial Intelligence, pp. 234-246. Springer, 2003.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Private Computations in Networks: Topology versus Randomness.
  In 21 GI Symposium on Theoretical Aspects of Computer Science STACS'2003, Volume 2607 of Lecture Notes in Computer Science, pp. 189-198. Springer, 2003.
  Go to website
• Bodo Manthey, Rüdiger Reischuk:
  The Intractability of Computing the Hamming Distance.
  In 14. Int. Symposium on Algorithms and Computation ISAAC'2003, Volume 2906 of Lecture Notes in Computer Science, pp. 88-97. Springer, 2003.
  Go to website
• Rüdiger Reischuk:
  Planung und Realisation von Informationssystemen: Algorithmische Komplexität.
  In Taschenbuch der Wirtschaftsinformatik und Wirtschaftsmathematik, Kap. 6.2, pp. 246-252. Harri Deutsch, 2003.
  Go to website

2002

• David Barrington, Johan Hastad, Matthias Krause, Rüdiger Reischuk:
  Complexity of Boolean Functions.
  Volume 02121 of Dagstuhl-Seminar-Report, Schloss Dagstuhl GmbH, 2002.
  Go to website
• H. Beilner, H. Fiedler, O. Günther, S. Hölldobler, G. Hotz, P. Liggesmeyer, K. Löhr, R. Reischuk, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2001.
  Volume D2 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2002.
  Go to website
• N. Cesa-Bianchi, M. Numao, R. Reischuk:
  Proceedings of the 13. Int. Conference on Algorithmic Learning Theory, ALT'2002.
  Volume 2533 of Lecture Notes in Computer Science, Springer, 2002.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Dynamic Process Graphs and the Complexity of Scheduling.
  Technical report SIIM-TR-A-00-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
  Show postscript | Show abstract
  
  In parallel and distributed computing scheduling low level tasks on the available hardware is a fundamental problem. Traditionally, one has assumed that the set of tasks to be executed is known beforehand. Then the scheduling constraints are given by a precedence graph. Nodes represent the elementary tasks and edges the dependencies among tasks. This static approach is not appropriate in situations where the set of tasks is not known exactly in advance, for example, when different options how to continue a program may be granted. In this paper a new model for parallel and distributed programs, the dynamic process graph, will be introduced, which represents all possible executions of a program in a compact way. The size of this representation is small -- in many cases only logarithmically with respect to the size of any execution. An important feature of our model is that the encoded executions are directed acyclic graphs having a 'regular' structure that is typical of parallel programs. Dynamic process graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. With respect to such a compact representation we investigate the complexity of different aspects of the scheduling problem: the question whether a legal schedule exists at all and how to find an optimal schedule. Our analysis takes into account communication delays between processors exchanging data. Precise characterization of the computational complexity of various variants of this compact scheduling problem will be given in this paper. The results range from easy, that is NL-complete, to very hard, namely NEXPTIME-complete. This is a revised and complete version of results discussed in TR A-98-07. An extended abstract of this paper has been presented at 16th International Symposium on Theoretical Aspects of Computer Science, Trier, Germany, 1999.
• Bodo Manthey, Rüdiger Reischuk:
  The Intractability of Computing the Hamming Distance.
  Technical report SIIM-TR-A-02-17, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
  Show postscript | Show abstract
  
  Given a language $L$, the Hamming distance of a string $x$ to $L$ is the minimum Hamming distance of $x$ to any string in $L$. The edit distance of a string to a given language is defined similarly. First, we prove that the Hamming distance to languages in $\AC^0$ is hard to approximate; it cannot be approximated within a factor $O\bigl(n^{\frac 13 - \epsilon}\bigr)$, for any $\epsilon > 0$, unless $\mathsf P = \mathsf{NP}$ ($n$ denotes the length of the input string). Second, we show the parameterised intractability of computing the Hamming distance. We prove that for every $t \in \nat$ there exists a language in $\AC^0$ such that the problem of computing the Hamming distance is $\mathsf W[t]$-hard. Moreover, there is a language in \DP\ such that computing the Hamming distance to it is $\mathsf W[P]$-hard. Furthermore, we show that the problems of computing the Hamming distance and of computing the edit distance are in some sense equivalent by presenting reductions from the former to the latter problem and vice versa.
• Rüdiger Reischuk:
  Average-case Computational Complexity.
  In Encyclopaedia of Mathematics, Suppl. III, pp. 111-128. Springer, 2002.

2001

• H. Fiedler, W. Grass, O. Günther, S. Hölldobler, G. Hotz, R. Reischuk, B. Seeger, D. Wagner:
  Ausgezeichnete Informatikdissertationen 2000.
  Volume D1 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2001.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Series-Parallel Graphs.
  In 18 GI-MIMD Symposium on Theoretical Aspects of Computer Science STACS'2001, Volume 2010 of Lecture Notes in Computer Science, pp. 339-352. Springer, 2001.
  Go to website

2000

• H. Fiedler, W. Grass, O. Günther, S. Hölldobler, G. Hotz, R. Reischuk, B. Seeger, D. Wagner:
  Ausgezeichnete Informatikdissertationen 1999.
  GI-Dissertationspreis, Teubner Verlag Stuttgart, Leipzig, 2000.
  Go to website
• Andreas Jakoby, Rüdiger Reischuk:
  Average Complexity of Unbounded Fanin Circuits.
  In 11. IEEE Conference on Computational Complexity COMPLEXITY'2000, pp. 170-185. IEEE Computer Society, 2000.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Series-Parallel Graphs.
  Technical report SIIM-TR-A-00-17, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2000.
  Show postscript | Show abstract
  
  The subclass of directed series-parallel graphs plays an important role in computer science. To determine whether a graph is series-parallel is a well studied problem in algorithmic graph theory. Fast sequential and parallel algorithms for this problem have been developed in a sequence of papers. For series-parallel graphs methods are also known to solve the reachability and the decomposition problem time efficiently. However, no dedicated results have been obtained for the space complexity of these problems -- the topic of this paper. For this special class of graphs, we develop deterministic algorithms for the recognition, reachability, decomposition and the path counting problem that use only logarithmic space. Since for arbitrary directed graphs reachability and path counting are believed not to be solvable in log-space the main contribution of this work are novel deterministic path finding routines that work correctly in series-parallel graphs, and a new characterization of series-parallel graphs by forbidden subgraphs. We then sketch how these results can be generalised to extension of the series-parallel graph family: to graphs with multiple sources or multiple sinks and to the class of minimal vertex series-parallel graphs. It it also shown that the space bounds are best possible, i.e. the decision problems are L-complete with respect to AC-reductions. Finally, we discuss implications of theses small space bounds for the parallel time complexity of series-parallel graphs.
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  The Expressive Power and Complexity of Dynamic Process Graphs.
  In 26. Int. Workshop on Graph-Theoretical Concepts in Computer Science WG'2000, Volume 1928 of Lecture Notes in Computer Science, pp. 230-242. Springer, 2000.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  The Expressive Power and Complexity of Dynamic Process Graphs.
  Technical report SIIM-TR-A-00-07, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2000.
  Show postscript | Show abstract
  
  A model for parallel and distributed programs, the dynamic process graph, is investigated under graph-theoretic and complexity aspects. Such graphs are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation is small -- in many cases only logarithmic with respect to the size of any execution of the program. An important feature of this model is that the encoded executions are directed acyclic graphs with a regular structure, which is typical of parallel programs, and that it embeds constructors for parallel programs, synchronization mechanisms as well as conditional branches. In a previous paper we have analysed the expressive power of the general model and various restrictions. Furthermore, from an algorithmic point of view it is important to decide whether a given dynamic process graph can be executed correctly and to estimate the minimal deadline given enough parallelism. Our model takes into account communication delays between processors when exchanging data. In this paper we study a variant with output restriction. It is appropriate in many situations, but its expressive power has not been known exactly. First, we investigate structural properties of the executions of such dynamic process graphs G. A natural graph-theoretic conjecture that executions must always split into components isomorphic to subgraphs of G turns out to be wrong. We are able to establish a weaker property. This implies a quadratic bound on the maximal deadline in contrast to the general case, where the execution time may be exponential. However, we show that the problem to determine the minimal deadline is still intractable, namely this problem is NEXPTIME-complete as is the general case. The lower bound is obtained by showing that this kind of dynamic process graphs can represent certain Boolean formulas in a highly succinct way. This is an extended abstract to be presented at 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, 2000.
• Rüdiger Reischuk, Thomas Zeugmann:
  An Average-Case Optimal One-Variable Pattern Language Learner.
  Journal of Computer and System Sciences, 2(60):302-335, 2000.
  Go to website
• Rüdiger Reischuk:
  Can Large Fanin Circuits Perform Reliable Computations in the Presence of Faults?
  Theoretical Computer Science, 2(240):319-335, 2000.
  Go to website
• Stephan Weis, Rüdiger Reischuk:
  The Complexity of Physical Mapping with Strict Chimerism.
  In 6. Int. Symposium on Computing and Combinatorics COCOON'2000, Volume 1858 of Lecture Notes in Computer Science, pp. 383-395. Springer, 2000.
  Go to website