- Wolfgang Paul, Ernst Prauss, Rüdiger Reischuk:
On Alternation.
In 19. IEEE Ann. Symposium on Foundations of Computer Science FOCS'78, S. 113-122.
IEEE Computer Society,
1978.
Website anzeigen - 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, S. 84-91.
IEEE Computer Society,
1978.
Website anzeigen - Wolfgang Paul, Rüdiger Reischuk:
On Alternation II - A Graph Theoretic Approach to Determinism versus Nondeterminism.
In 4. GI Tagung on Theoretical Computer Science, Band 67 von Lecture Notes in Computer Science, S. 222-232.
Springer,
1979.
Website anzeigen - Wolfgang Paul, Rüdiger Reischuk:
On Time versus Space II.
In 20. IEEE Ann. Symposium on Foundations of Computer Science FOCS'79, S. 298-306.
IEEE Computer Society,
1979.
Website anzeigen - 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, Band 85 von Lecture Notes in Computer Science, S. 531-542.
Springer,
1980.
Website anzeigen - Rüdiger Reischuk:
Probabilistic Parallel Algorithms for Sorting and Selection.
In 22. IEEE Ann. Symposium on Foundations of Computer Science FOCS'81, S. 212-219.
IEEE Computer Society,
1981.
Website anzeigen - Danny Dolev, Rüdiger Reischuk, Ray Strong:
'Eventual' is Earlier than 'Immediate'.
In 23. IEEE Ann. Symposium on Foundations of Computer Science FOCS'82, S. 196-203.
IEEE Computer Society,
1982.
Website anzeigen - Danny Dolev, Rüdiger Reischuk:
Bounds on Information Exchange for Byzantine Agreement.
In 1. ACM Symposium on Principles of Distributed Computing PODC'82, S. 132-140.
ACM Association for Computing Machinery,
1982.
Website anzeigen - Pavol Duris, Zvi Galil, Wolfgang Paul, Rüdiger Reischuk:
Two Nonlinear Lower Bounds.
In 15. ACM Symposium on Theory of Computing STOC'83, S. 127-132.
ACM Association for Computing Machinery,
1983.
Website anzeigen - Rüdiger Reischuk:
A New Solution for the Byzantine Generals Problem.
In 5. Int. Conference on Foundations of Computation Theory FCT'83, Band 158 von Lecture Notes in Computer Science, S. 382-393.
Springer,
1983.
Website anzeigen - 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, S. 56-64.
IEEE Computer Society,
1984.
Website anzeigen - Rüdiger Reischuk:
Parallel Machines and their Communication Theoretical Limits.
In 3. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'86, Band 210 von Lecture Notes in Computer Science, S. 359-368.
Springer,
1986.
Website anzeigen - 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, S. 337-346.
IEEE Computer Society,
1987.
Website anzeigen - 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, Band 312 von Lecture Notes in Computer Science, S. 374-387.
Springer,
1987.
Website anzeigen - Rüdiger Reischuk:
Konsistenz und Fehlertoleranz in Verteilten Systemen - Das Problem der Byzantinischen Generäle.
In 17. GI Jahrestagung 1987, Band 156 von Springer Informatik Fachberichte, S. 65-81.
Springer,
1987.
Website anzeigen - Bernd Halstenberg, Rüdiger Reischuk:
Relations between Communication Complexity Classes.
In 3. Ann. IEEE - SIGACT - EATCS Symposium on Structure in Complexity Theory STRUCTURES'88, S. 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, Band 349 von Lecture Notes in Computer Science, S. 314-326.
Springer,
1989.
Website anzeigen - 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, S. 125-135.
ACM Association for Computing Machinery,
1990.
Website anzeigen - Rüdiger Reischuk:
Graph Theoretical Methods for the Design of Parallel Algorithms.
In 8. Conference on Fundamentals of Computation Theory FCT'91, Band 529 von Lecture Notes in Computer Science, S. 61-67.
Springer,
1991.
Website anzeigen - 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, S. 602-611.
IEEE Computer Society,
1991.
Website anzeigen - Andreas Jakoby, Rüdiger Reischuk:
The Complexity of Scheduling Problems with Communication Delays for Trees.
In 3. Skandinavian Workshop on Algorithmic Theory SWAT'92, Band 621 von Lecture Notes in Computer Science, S. 165-177.
Springer,
1992.
Website anzeigen - 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, Band 665 von Lecture Notes in Computer Science, S. 16-27.
Springer,
1993.
Website anzeigen - Rüdiger Reischuk, Christian Schindelhauer:
Precise Average Case Complexity.
In 10. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'93, Band 665 von Lecture Notes in Computer Science, S. 650-661.
Springer,
1993.
Website anzeigen - Danny Dolev, Rüdiger Reischuk, Ray Strong:
Observable Clock Synchronisation.
In 14. ACM Symposium on Principles of Distributed Computing PODC'94, S. 284-293.
ACM Association for Computing Machinery,
1994.
Website anzeigen - 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, S. 58-67.
ACM Association for Computing Machinery,
1994.
Website anzeigen - 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, Band 820 von Lecture Notes in Computer Science, S. 593-604.
Springer,
1994.
Website anzeigen - 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, Band 903 von Lecture Notes in Computer Science, S. 219-231.
Springer,
1994.
Website anzeigen - 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, S. 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, Band 972 von Lecture Notes in Computer Science, S. 145-159.
Springer,
1995.
Website anzeigen - 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, Band 900 von Lecture Notes in Computer Science, S. 628-639.
Springer,
1995.
Website anzeigen - 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, Band 1295 von Lecture Notes in Computer Science, S. 91-107.
Springer,
1997.
Website anzeigen - 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, Band 1276 von Lecture Notes in Computer Science, S. 72-81.
Springer,
1997.
Website anzeigen - Rüdiger Reischuk, Thomas Zeugmann:
Learning One-Variable Pattern Languages in Linear Average Time.
In 11. Conf. on Computational Learning Theory COLT'98, S. 198-208.
,
1998.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Scheduling Dynamic Graphs.
In 16. GI-MIMD Symposium on Theoretical Aspects of Computer Science STACS'99, Band 1563 von Lecture Notes in Computer Science, S. 383-393.
Springer,
1999.
Website anzeigen - 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, Band 1563 von Lecture Notes in Computer Science, S. 414-423.
Springer,
1999.
Website anzeigen - Andreas Jakoby, Rüdiger Reischuk:
Average Complexity of Unbounded Fanin Circuits.
In 11. IEEE Conference on Computational Complexity COMPLEXITY'2000, S. 170-185.
IEEE Computer Society,
2000.
Website anzeigen - 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, Band 1928 von Lecture Notes in Computer Science, S. 230-242.
Springer,
2000.
Website anzeigen - Stephan Weis, Rüdiger Reischuk:
The Complexity of Physical Mapping with Strict Chimerism.
In 6. Int. Symposium on Computing and Combinatorics COCOON'2000, Band 1858 von Lecture Notes in Computer Science, S. 383-395.
Springer,
2000.
Website anzeigen - 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, Band 2010 von Lecture Notes in Computer Science, S. 339-352.
Springer,
2001.
Website anzeigen - Jan Arpe, Rüdiger Reischuk:
Robust Inference of Funtional Relations.
In 14 Int. Conference on Algorithmic Learning Theory ALT'2003, Band 2842 von Lecture Notes in Artificial Intelligence, S. 99-113.
Springer,
2003.
Website anzeigen - 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, Band 2842 von Lecture Notes in Artificial Intelligence, S. 234-246.
Springer,
2003.
Website anzeigen - 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, Band 2607 von Lecture Notes in Computer Science, S. 189-198.
Springer,
2003.
Website anzeigen - Bodo Manthey, Rüdiger Reischuk:
The Intractability of Computing the Hamming Distance.
In 14. Int. Symposium on Algorithms and Computation ISAAC'2003, Band 2906 von Lecture Notes in Computer Science, S. 88-97.
Springer,
2003.
Website anzeigen - 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, S. 307-312.
IEEE Computer Society,
2004.
Website anzeigen - Jan Arpe, Rüdiger Reischuk:
Learning Juntas in the Presence of Noise.
In Proc. Theory and Applications of Models of Computation TAMC'2006, Band 3959 von Lecture Notes in Computer Science, S. 387-398.
Springer,
2006.
Website anzeigen - Jan Arpe, Rüdiger Reischuk:
On the Complexity of Optimal Grammar Based Compression.
In Proc. 16. Data Compression Conference DCC'2006, S. 173-182.
IEEE Computer Society,
2006.
Website anzeigen - 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, Band 4598 von Lecture Notes in Computer Science, S. 296-306.
Springer,
2007.
Website anzeigen - 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, Band 4484 von Lecture Notes in Computer Science, S. 330-341.
Springer,
2007.
Website anzeigen - 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, S. 476.
IEEE Computer Society,
2008.
Website anzeigen - Florian Thaeter, Rüdiger Reischuk:
Improving Time Complexity and Utility of k-anonymous Microaggregation.
In E-Business and Telecommunications, 18.~Int. Conference ICETE 2021, Band 1795 von Communications in Computer and Information Science, S. 195-223.
Springer,
2023.
- Rüdiger Reischuk:
The Kangaroo Problem.
Band 898 von Theoretical Computer Science, S. 50-58.
Elsevier,
2022.
Website anzeigen - Florian Thaeter, Rüdiger Reischuk:
Hardness of k-anonymous Microaggregation.
Band 303 von Discrete Applied Mathematics, S. 149-158.
Elsevier,
2022.
Website anzeigen - 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), Band 214 von LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2021.
Website anzeigen | Zusammenfassung anzeigen
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), S. 87-98.
SCITEPRESS,
2021.
Zusammenfassung anzeigen
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, S. 69-72.
Inproceedings,
2019.
PDF anzeigen - Florian Thaeter, Rüdiger Reischuk:
Improving Anonymization Clustering.
In SICHERHEIT 2018, S. 69-82.
Gesellschaft für Informatik e.V.,
2018.
Website anzeigen - 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.
- 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, Band Volume 9618 von Lecture Notes in Computer Science (LNCS), S. 387-399.
Springer,
2016.
Website anzeigen | Zusammenfassung anzeigen
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), 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.
- Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Grey-Box Steganography.
Band 6648 von Lecture Notes in Computer Science, S. 390-402.
Springer Verlag, Heidelberg, in Proceedings 8. TAMC,
2011.
Website anzeigen - 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), Band 6825 von Lecture Notes in Computer Science, S. 146-159.
Springer,
2011.
