- Wolfgang Paul, Rüdiger Reischuk:
On Alternation II - A Graph Theoretic Approach to Determinism versus Nondeterminism.
Acta Informatica, 4(14):391-403, 1980.
Go to website - Wolfgang Paul, Ernst Prauss, Rüdiger Reischuk:
On Alternation.
Acta Informatica, 3(14):243-255, 1980.
Go to website - Rüdiger Reischuk:
Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game.
Journal of the ACM, 4(27):839-849, 1980.
Go to website - Rüdiger Reischuk:
A Fast Implementation of a Multidimensional Storage into a Tree Storage.
Theoretical Computer Science, 3(19):253-266, 1982.
Go to website - Pavol Duri, Zvi Galil, Wolfgang Paul, Rüdiger Reischuk:
Two Nonlinear Lower Bounds.
Information and Control, 1-3(60):1-11, 1984.
Go to website - F.R.K. Chung, R.E. Tarjan, W.J. Paul, R. Reischuk:
Coding Strings by Pairs of Strings.
SIAM Journal on Matrix Analysis and Applications, 3(6):445-461, 1985.
Go to website - Danny Dolev, Rüdiger Reischuk:
Bounds on Information Exchange for Byzantine Agreement.
Journal of the ACM, 1(32):191-204, 1985.
Go to website - Rüdiger Reischuk:
A New Solution for the Byzantine Generals Problem.
Information and Control, 1-3(64):23-42, 1985.
Go to website - Rüdiger Reischuk:
Probabilistic Parallel Algorithms for Sorting and Selection.
SIAM Journal on Computing, 1(14):396-409, 1985.
Go to website - Steve Cook, Cynthia Dwork, Rüdiger Reischuk:
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes.
SIAM Journal on Computing, 1(15):87-97, 1986.
Go to website - Rüdiger Reischuk:
Simultaneous Writes of Parallel Random Access Machines Do not Help to Compute Simple Arithmetic Functions.
Journal of the ACM, (34):163-178, 1987.
Go to website - Rüdiger Reischuk:
Parallele Rechnermodelle und Komplexitätsklassen.
Informationstechnik IT, (31):59-77, 1989.
- Hagit Attiya, A. Bar-Noy, Danny Dolev, David Peleg, Rüdiger Reischuk:
Renaming in an Asynchronous Environment.
Journal of the ACM, 3(37):524-548, 1990.
Go to website - Danny Dolev, Rüdiger Reischuk, Ray Strong:
Early Stopping in Byzantine Agreement.
Journal of the ACM, 4(37):720-741, 1990.
Go to website - Bernd Halstenberg, Rüdiger Reischuk:
Relations between Communication Complexity Classes.
Journal of Computer and System Sciences, 3(41):402-429, 1990.
Go to website - Bernd Halstenberg, Rüdiger Reischuk:
Different Modes of Communication.
SIAM Journal on Computing, 5(22):913-934, 1993.
Go to website - Martin Dietzfelbinger, Mirek Kutylowski, Rüdiger Reischuk:
Feasable Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines.
SIAM Journal on Computing, 6(25):1196-1230, 1996.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
The Sublogarithmic Alternating Space World.
SIAM Journal on Computing, 4(25):828-861, 1996.
Go to website - Rüdiger Reischuk, Christian Schindelhauer:
An Average Complexity Measure that Yields Tight Hierarchies.
Computational Complexity, 2(6):133-173, 1996.
Go to website - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
The Complexity of Broadcasting in Planar and Decomposable Graphs.
Discrete Applied Mathematics, 1-3(83):179-206, 1998.
Go to website | Show abstract
[URL=http://www.elsevier.com/wps/find/journaldescription.cws_home/505609/description#description]also included in special issue "Discrete Applied Mathematics - Editors' Choice 1988[/URL]
- Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Malign Distributions for Average Case Circuit Complexity.
Information and Computation, 2(150):187-208, 1999.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
On Small Space Complexity Classes of Stochastic Turing Machines and Arthur-Merlin-Games.
Computational Complexity, 3(8):273-307, 1999.
Go to website - 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 - 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 - Bodo Manthey, Rüdiger Reischuk:
The Intractability of Computing the Hamming Distance.
Theoretical Computer Science, 1-3(337):331-346, 2005.
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 - Jan Arpe, Rüdiger Reischuk:
Learning Juntas in the Presence of Noise.
Theoretical Computer Science, 1(384):2-21, 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.
- 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 - 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, 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."
- 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.
- 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.
- 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 - 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.
- Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Grey-box steganography.
Theoretical Computer Science, (505):27-41, 2013.
Go to website
