All reports by Author Rüdiger Reischuk:

__
TR06-065
| 24th May 2006
__

Jan Arpe, Rüdiger Reischuk#### When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---

__
TR05-063
| 24th June 2005
__

Bodo Manthey, Rüdiger Reischuk#### Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

__
TR04-038
| 27th April 2004
__

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann#### A Polynomial Time Learner for a Subclass of Regular Patterns

__
TR02-021
| 11th April 2002
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Space Efficient Algorithms for Directed Series-Parallel Graphs

__
TR01-090
| 28th November 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Dynamic Process Graphs and the Complexity of Scheduling

__
TR01-038
| 14th May 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Approximating Schedules for Dynamic Graphs Efficiently

__
TR98-070
| 7th December 1998
__

Rüdiger Reischuk#### Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

__
TR98-069
| 7th December 1998
__

Rüdiger Reischuk, Thomas Zeugmann#### An Average-Case Optimal One-Variable Pattern Language Learner

__
TR95-005
| 1st January 1995
__

Maciej Liskiewicz, Rüdiger Reischuk#### The Sublogarithmic Alternating Space World

__
TR95-004
| 1st January 1995
__

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk#### Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

Jan Arpe, Rüdiger Reischuk

Detecting the relevant attributes of an unknown target concept

is an important and well studied problem in algorithmic learning.

Simple greedy strategies have been proposed that seem to perform reasonably

well in practice if a sufficiently large random subset of examples of the target

concept is provided.

Introducing a ... more >>>

Bodo Manthey, Rüdiger Reischuk

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

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

Presented is an algorithm (for learning a subclass of erasing regular

pattern languages) which

can be made to run with arbitrarily high probability of

success on extended regular languages generated by patterns

$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$

for unknown $m$ but known $c$,

more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

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 fast sequential and

parallel algorithms have been developed in a sequence of papers.

Also methods are known to solve ...
more >>>

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

Then the scheduling constraints are given by a precedence graph.

Nodes represent the elementary tasks ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

A model for parallel and distributed programs, the dynamic process graph (DPG),

is investigated under graph-theoretic and complexity aspects.

Such graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

They are capable of representing all possible executions of a

parallel or distributed program ...
more >>>

Rüdiger Reischuk

For ordinary circuits with a fixed upper bound on the maximal fanin

of gates it has been shown that logarithmic redundancy is necessary and

sufficient to overcome random hardware faults.

Here, we consider the same question for unbounded fanin circuits that

in the noiseless case can compute ...
more >>>

Rüdiger Reischuk, Thomas Zeugmann

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 account all

operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions

defining how ...
more >>>

Maciej Liskiewicz, Rüdiger Reischuk

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,

nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ...
more >>>

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

It was shown some years ago that the computation time for many important

Boolean functions of n arguments on concurrent-read exclusive-write

parallel random-access machines

(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.

On the other hand, it ...
more >>>