Rüdiger Reischuk

The Intractability of Computing the Hamming Distance (2008)

Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined. First,...

08381 Executive Summary -- Computational Complexity of Discrete Problems (2008)

Abstract. Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously...

Miltersen, Peter Bro, Reischuk, Rüdiger, Schnitger, Georg, Van Melkebeek, Dieter

Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried...

08381 Abstracts Collection -- Computational Complexity of Discrete Problems (2008)

Miltersen, Peter Bro, Reischuk, Rüdiger, Schnitger, Georg, Van Melkebeek, Dieter

From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During...

The Complexity World below Logarithmic Space (2007)

Data Transmission in Processor Networks (2007)

We investigate space complexity classes defined by Turing machines that use less than logarithmic space. Because of the limited counting ability of such machines most of the standard simulation...

Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds (2007)

. We investigate the communication capacity and optimal data transmission schedules for processor networks connected by communication links, for example Transputer clusters. Each link allows the two...

The Intractability of Computing the Hamming Distance (2007)

. A Stochastic Turing machine (STM) is a Turing machine that can perform nondeterministic and probabilistic moves and alternate between both types. Such devices are also called games against nature,...

Rüdiger Reischuk, Serie A, Technisch-naturwissenschaftliche Fakultat, Bodo Manthey, Bodo Manthey, Rudiger Reischuk

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.

Knowledge State Algorithms: Randomization with Limited Information (2007)

Bein, Wolfgang, Larmore, Lawrence L., Reischuk, Rüdiger

We introduce the concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to to construct competitive randomized...

Learning Juntas in the Presence of Noise ∗ (2007)

Jan Arpe, Rüdiger Reischuk

We investigate the combination of two major challenges in computational learning: dealing with huge amounts of irrelevant information and learning from noisy data. It is shown that large classes of...

Learning a subclass of regular patterns in polynomial time (2006)

Case, John, Jain, Sanjay, Reischuk, Rüdiger, Stephan, Frank, Zeugmanne, Thomas

An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of the form xoaıxı…amxm, where xo,…,xm are...

Learning a subclass of regular patterns in polynomial time (2006)

Case, John, Jain, Sanjay, Reischuk, Rüdiger, Stephan, Frank, Zeugmanne, Thomas

An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of the form xoaıxı…amxm, where xo,…,xm are...

aus der Technisch-Naturwissenschaftlichen Fakultät (2006)

Frank Balbach, Direktor Prof, Dr. Rüdiger Reischuk, Frank Balbach

Learning theory focuses almost entirely on the learner and its efficient realization, but neglects other parts of the learning process, most importantly the teacher, which is merely modeled as a...

aus der Technisch-Naturwissenschaftlichen Fakultät (2006)

Jan Arpe, Jan Arpe, Berichterstatter Prof, Dr. Rüdiger Reischuk, Prof Dr, ...

In the first place, I would like to thank my Doktorvater Rüdiger Reischuk for giving me the opportunity to work and to carry out my research at the Institut für Theoretische Informatik of the...

R.: Space efficient algorithms for directed series-parallel graphs (2006)

06111 Abstracts Collection -- Complexity of Boolean Functions (2006)

The subclass of directed series-parallel graphs plays an important role in computer science. Whether a given graph is series-parallel is a well studied problem in algorithmic graph theory, for which...

Krause, Matthias, Pudlák, Pavel, Reischuk, Rüdiger, Van Melkebeek, Dieter

From 12.03.06 to 17.03.06, the Dagstuhl Seminar 06111 ``Complexity of Boolean Functions'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar,...

06111 Executive Summary -- Complexity of Boolean Functions (2006)

Krause, Matthias, Van Melkebeek, Dieter, Pudlák, Pavel, Reischuk, Rüdiger

We briefly describe the state of the art concerning the complexity of discrete functions. Computational models and analytical techniques are summarized. After describing the formal organization of...

Smoothed analysis of binary search trees (2005)

Informatik/Mathematik (2005)

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

Jan Arpe, Bodo Manthey, Rüdiger Reischuk, Serie B, ...

Gesellschaft für Informatik (GI) veranstaltet. Er ermöglicht einen intensiven Dialog

R.: Smoothed analysis of binary search trees (2005)

On the Complexity of Optimal Grammar-Based Compression (2004)

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

Jan Arpe, Rüdiger Reischuk, Serie A, Technisch-naturwissenschaftliche Fakultät, Jan Arpe, ...

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

Average Case Complexity of Unbounded Fanin Circuits (2000)

An Average-Case Optimal One-Variable Pattern Language Learner (2000)

Several authors have shown that the PARITY-function cannot be computed by unbounded fanin circuits of small depth and polynomial size. Even more, constant depth k circuits of size exp(n \Theta(1=k) )...

An Average-Case Optimal One-Variable Pattern Language Learner (2000)

A new algorithm for learning one-variable pattern languages from positive data is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into...

A complete and tight average-case analysis of learning monomials (1999)

A new algorithm for learning one-variable pattern languages from positive data is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into...

Analysing Data Access Strategies in Cache Coherent Architectures (1999)

Abstract. We advocate to analyze the average complexity of learning problems. An appropriate framework for this purpose is introduced. Based on it we consider the problem of learning monomials and...

Karin Genther, Rüdiger Reischuk

. The conception of multiprocessor systems based on shared memory is to provide logically uniform data access, even in systems with many processors. Since data requests that cannot be satisfied...

A Complete and Tight Average-Case Analysis of Learning Monomials (1999)

Analyzing the Average-Case Behavior of Conjunctive Learning Algorithms (1998)

. We advocate to analyze the average complexity of learning problems. An appropriate framework for this purpose is introduced. Based on it we consider the problem of learning monomials and the...

Reischuk, Rüdiger, Zeugmann, Thomas

We advocate to analyze the average complexity of learning problems. An appropriate framework for this purpose is introduced. Based on it we consider the problem of learning monomials and the special...

Learning one-variable pattern languages in linear average time (1998)

Rüdiger Reischuk

A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all...

Scheduling Dynamic Graphs (1998)

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

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

A Complete and Tight Average-Case Analysis of Learning Monomials (1998)

Average Case Complexity of Unbounded Fanin Circuits (1998)

We advocate to analyze the average complexity of learning problems. An appropriate framework for this purpose is introduced. Based on it we consider the problem of learning monomials and the special...

Can Large Fanin Circuits Perform Reliable Computations in the Presence of Faults? (1998)

Hastad has shown that functions like PARITY cannot be computed by unbounded fanin circuits of small depth and polynomial size. We generalize this result in two directions. First, we obtain the same...

Rüdiger Reischuk

For ordinary circuits with a fixed upper bound on the fanin of its gates it has been shown that logarithmic redundancy is necessary and sufficient to overcome random hardware faults (noise). Here, we...

Learning One-Variable Pattern Languages in Linear Average Time (1997)

Reischuk, Rüdiger, Zeugmann, Thomas

A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all...

Learning One-Variable Pattern Languages in Linear Average Time (1997)

Learning One-Variable Pattern Languages in Linear Average Time (1997)

A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all...

Scheduling Trees with Communication Delays (1997)

A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all...

Computing with Sublogarithmic Space (1997)

Several variants of scheduling task graphs with interprocessor communication delays have been shown to be NP -complete. This paper completely characterizes the complexity of this problem under the...

Learning One-Variable Pattern Languages in Linear Average Time (1997)

We investigate space complexity classes defined by Turing machines that use less than logarithmic space. Because of the limited counting ability of such machines most of the standard simulation...

Rüdiger Reischuk, R Udiger Reischuk, Thomas Zeugmann, Thomas Zeugmann

A new algorithm for learning one-variable pattern languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all...

Separating Small Space Complexity Classes of Stochastic Turing Machines (1996)

Space Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds (1996)

Stochastic Turing machines are Turing machines that can perform nondeterministic and probabilistic moves. Such devices are also called games against nature, Arthur-Merlin games, or interactive proof...

The Sublogarithmic Alternating Space World (1996)

This paper studies interactive proof systems using public coin tosses, respectively Arthur-Merlin games, with a sublogarithmic space-bounded verifier. We provide examples of specific languages and...

Malign Distributions for Average Case Circuit Complexity (1995)

. This paper tries to fully characterize the properties and relationships of space classes defined by Turing machines that use less than logarithmic space -- may they be deterministic,...

Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance,...

The Complexity of Broadcasting in Planar and Decomposable Graphs (1995)

Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer

Broadcasting in processor networks means disseminating a single piece of information, which is originally known only at some nodes, to all members of the network. The goal is to inform everybody...

A Decentralized High Performance Time Service Architecture (1995)

Danny Dolev, Rüdiger Reischuk, Ray Strong, Ed Wimmers

A time service is a means by which users, applications, etc. obtain values associated with some measurement of elapsed time from some agreed on event. In a relativistic world, time services are...

Malign Distributions for Average Case Circuit Complexity (Extended Abstract) (1995)

Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer

In contrast to machine models like Turing machines or random access machines, circuits are a rigid computational model. The internal information flow of a computation is fixed in advance, independent...

Circuit Complexity: from the Worst Case to the Average Case (1994)

Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer

In contrast to machine models like Turing machines or random access machines, circuits are a rigid computational model. The internal information flow of a computation is fixed in advance, independent...

Observable Clock Synchronization (1994)

Danny Dolev, Rüdiger Reischuk, Ray Strong

While the synchronization of time-of-day clocks ordinarily requires information flow in both directions between the clocks, this information need not flow directly via messages. However, to take...

The Complexity World below Logarithmic Space (1994)