- Wolfgang Paul, Ernst Prauss, Rüdiger Reischuk:
On Alternation.
In 19. IEEE Ann. Symposium on Foundations of Computer Science FOCS'78, pp. 113-122.
IEEE Computer Society,
1978.
Go to website - Rüdiger Reischuk:
Improved Bounds on the Problem of Time-Space Trade-Offs in the Pebble Game.
In 19. IEEE Ann. Symposium on Foundations of Computer Science FOCS'78, pp. 84-91.
IEEE Computer Society,
1978.
Go to website - Wolfgang Paul, Rüdiger Reischuk:
On Alternation II - A Graph Theoretic Approach to Determinism versus Nondeterminism.
In 4. GI Tagung on Theoretical Computer Science, Volume 67 of Lecture Notes in Computer Science, pp. 222-232.
Springer,
1979.
Go to website - Wolfgang Paul, Rüdiger Reischuk:
On Time versus Space II.
In 20. IEEE Ann. Symposium on Foundations of Computer Science FOCS'79, pp. 298-306.
IEEE Computer Society,
1979.
Go to website - Rüdiger Reischuk:
A Fast Implementation of a Multidimensional Storage into a Tree Storage.
In 7. EATCS International Colloquium on Automata Theory, Languages and Computation ICALP'80, Volume 85 of Lecture Notes in Computer Science, pp. 531-542.
Springer,
1980.
Go to website - Rüdiger Reischuk:
Probabilistic Parallel Algorithms for Sorting and Selection.
In 22. IEEE Ann. Symposium on Foundations of Computer Science FOCS'81, pp. 212-219.
IEEE Computer Society,
1981.
Go to website - Danny Dolev, Rüdiger Reischuk, Ray Strong:
'Eventual' is Earlier than 'Immediate'.
In 23. IEEE Ann. Symposium on Foundations of Computer Science FOCS'82, pp. 196-203.
IEEE Computer Society,
1982.
Go to website - Danny Dolev, Rüdiger Reischuk:
Bounds on Information Exchange for Byzantine Agreement.
In 1. ACM Symposium on Principles of Distributed Computing PODC'82, pp. 132-140.
ACM Association for Computing Machinery,
1982.
Go to website - Pavol Duris, Zvi Galil, Wolfgang Paul, Rüdiger Reischuk:
Two Nonlinear Lower Bounds.
In 15. ACM Symposium on Theory of Computing STOC'83, pp. 127-132.
ACM Association for Computing Machinery,
1983.
Go to website - Rüdiger Reischuk:
A New Solution for the Byzantine Generals Problem.
In 5. Int. Conference on Foundations of Computation Theory FCT'83, Volume 158 of Lecture Notes in Computer Science, pp. 382-393.
Springer,
1983.
Go to website - Friedhelm Meyer auf der Heide, Rüdiger Reischuk:
On the Limits to Speed up Parallel Machines by Large Hardware and Unbounded Communication.
In 25. Ann. IEEE Symposium on Foundations of Computer Science FOCS'84, pp. 56-64.
IEEE Computer Society,
1984.
Go to website - Rüdiger Reischuk:
Parallel Machines and their Communication Theoretical Limits.
In 3. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'86, Volume 210 of Lecture Notes in Computer Science, pp. 359-368.
Springer,
1986.
Go to website - Hagit Attiya, A. Bar-Noy, Danny Dolev, David Peleg, Rüdiger Reischuk:
Achievable Cases in an Asynchronous Environment.
In 28. Ann. Symposium on Foundations of Computer Science FOCS'87, pp. 337-346.
IEEE Computer Society,
1987.
Go to website - Meinolf Koshors, Rüdiger Reischuk:
Lower Bounds for Synchronous Systems and the Advantage of Local Information.
In 2. Int. Workshop on Distributed Algorithms WDAG'87, Volume 312 of Lecture Notes in Computer Science, pp. 374-387.
Springer,
1987.
Go to website - Rüdiger Reischuk:
Konsistenz und Fehlertoleranz in Verteilten Systemen - Das Problem der Byzantinischen Generäle.
In 17. GI Jahrestagung 1987, Volume 156 of Springer Informatik Fachberichte, pp. 65-81.
Springer,
1987.
Go to website - Bernd Halstenberg, Rüdiger Reischuk:
Relations between Communication Complexity Classes.
In 3. Ann. IEEE - SIGACT - EATCS Symposium on Structure in Complexity Theory STRUCTURES'88, pp. 19-28.
IEEE Computer Society,
1988.
- Rüdiger Reischuk, Bernd Schmeltz:
Area Efficient Methods to Increase the Reliability of Combinatorial Circuits.
In 6. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'89, Volume 349 of Lecture Notes in Computer Science, pp. 314-326.
Springer,
1989.
Go to website - Martin Dietzfelbinger, Mirek Kutylowski, Rüdiger Reischuk:
Exact Time Bounds for Computing Boolean Functions on PRAMs without Simultaneous Writes.
In 2. ACM Symposium on Parallel Algorithms and Architectures SPAA'90, pp. 125-135.
ACM Association for Computing Machinery,
1990.
Go to website - Rüdiger Reischuk:
Graph Theoretical Methods for the Design of Parallel Algorithms.
In 8. Conference on Fundamentals of Computation Theory FCT'91, Volume 529 of Lecture Notes in Computer Science, pp. 61-67.
Springer,
1991.
Go to website - Rüdiger Reischuk, Bernd Schmeltz:
Reliable Computation with Noisy Circuits and Decision Trees - A General n log n Lower Bound.
In 32. Ann. IEEE Conference on Foundations of Computer Science FOCS'91, pp. 602-611.
IEEE Computer Society,
1991.
Go to website - Andreas Jakoby, Rüdiger Reischuk:
The Complexity of Scheduling Problems with Communication Delays for Trees.
In 3. Skandinavian Workshop on Algorithmic Theory SWAT'92, Volume 621 of Lecture Notes in Computer Science, pp. 165-177.
Springer,
1992.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
Separating the Lower Levels of the Sublogarithmic Space Hierarchy.
In 10. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'93, Volume 665 of Lecture Notes in Computer Science, pp. 16-27.
Springer,
1993.
Go to website - Rüdiger Reischuk, Christian Schindelhauer:
Precise Average Case Complexity.
In 10. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'93, Volume 665 of Lecture Notes in Computer Science, pp. 650-661.
Springer,
1993.
Go to website - Danny Dolev, Rüdiger Reischuk, Ray Strong:
Observable Clock Synchronisation.
In 14. ACM Symposium on Principles of Distributed Computing PODC'94, pp. 284-293.
ACM Association for Computing Machinery,
1994.
Go to website - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Circuit Complexity: from the Worst Case to the Average Case.
In 26. Ann. ACM Symposium on Theory of Computing, pp. 58-67.
ACM Association for Computing Machinery,
1994.
Go to website - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer, Stephan Weis:
The Average Case Complexity of the Parallel Prefix Problem.
In EATCS Int. Colloquium on Automata Theory, Languages and Computation ICALP'94, Volume 820 of Lecture Notes in Computer Science, pp. 593-604.
Springer,
1994.
Go to website - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
The Complexity of Broadcasting in Planar and Decomposable Graphs.
In 20. Int. Workshop on Graph-Theoretic Concepts in Computer Science WG'94, Volume 903 of Lecture Notes in Computer Science, pp. 219-231.
Springer,
1994.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
The Complexity World below Logarithmic Space.
In 9. Ann. IEEE - SIGACT - EATCS Symposium on Structure in Complexity Theory STRUCTURES'94, pp. 64-78.
IEEE Computer Society,
1994.
- Andreas Jakoby, Rüdiger Reischuk:
Data Transmission in Processor Networks.
In 9. International Workshop on Distributed Algorithms WDAG'95, Volume 972 of Lecture Notes in Computer Science, pp. 145-159.
Springer,
1995.
Go to website - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Malign Distributions for Average Case Circuit Complexity.
In 12. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'95, Volume 900 of Lecture Notes in Computer Science, pp. 628-639.
Springer,
1995.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds.
In 22. Int. Symposium on Mathematical Foundations of Computer Science MFCS'97, Volume 1295 of Lecture Notes in Computer Science, pp. 91-107.
Springer,
1997.
Go to website - Rüdiger Reischuk:
Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?
In 3. Int. Symposium on Computing and Combinatorics COCOON'97, Volume 1276 of Lecture Notes in Computer Science, pp. 72-81.
Springer,
1997.
Go to website - Rüdiger Reischuk, Thomas Zeugmann:
Learning One-Variable Pattern Languages in Linear Average Time.
In 11. Conf. on Computational Learning Theory COLT'98, pp. 198-208.
,
1998.
Go to website - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Scheduling Dynamic Graphs.
In 16. GI-MIMD Symposium on Theoretical Aspects of Computer Science STACS'99, Volume 1563 of Lecture Notes in Computer Science, pp. 383-393.
Springer,
1999.
Go to website - Rüdiger Reischuk, Thomas Zeugmann:
A Complete and Tight Average-Case Analysis of Learning Monomials.
In 16. GI-MIMD Symposium on Theoretical Aspects of Computer Science STACS'99, Volume 1563 of Lecture Notes in Computer Science, pp. 414-423.
Springer,
1999.
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:
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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Rüdiger Reischuk:
Designing Boolean Sorting Circuits with Optimal Average Delay.
In Oberwolfach Reports X, Mathematisches Forschungsinstitut Oberwolfach,
2007.
- 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 - 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.
- 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 - 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.
- 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 - Florian Thaeter, Rüdiger Reischuk:
Improving Anonymization Clustering.
In SICHERHEIT 2018, pp. 69-82.
Gesellschaft für Informatik e.V.,
2018.
Go to website - 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.
- 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.
- 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:
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, 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.
