Proposed Running Text: Average Case Circuit Complexity (2007)
Andreas Jakoby, Rudiger 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,...
Miros/law Kuty/lowski z (2007)
Martin Dietzfelbinger, Heinz Nixdorf, Fachbereich Mathematik-informatik, Rudiger Reischuk
y Partially supported by DFG grant ME 872/1-4 and by DFG-Forschergruppe "Effiziente Nutzung paralleler
Proposed Running Text: Average Case Circuit Complexity (2007)
Andreas Jakoby, Rudiger 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 Expressive Power and Complexity of Dynamic Process Graphs (2007)
Andreas Jakoby, Rudiger Reischuk
Abstract. A model for parallel and distributed programs, the dynamic process graph, is investigated under graph-theoretic and complexity aspects. Such graphs are capable of representing all possible...
The Expressive Power and Complexity of Dynamic Process Graphs (2007)
Andreas Jakoby, Rudiger Reischuk
A model for parallel and distributed programs, the dynamic process graph, is investigated under graph-theoretic and complexity aspects. Such graphs are capable of representing all possible executions...
Dynamic Process Graphs and the Complexity of Scheduling (2007)
Andreas Jakoby, Rudiger 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...
Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise? (2007)
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...
The Intractability of Computing the Hamming Distance (2007)
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.
Space efficient algorithms for series-parallel graphs (2001)
Andreas Jakoby, Maciej Liskiewicz, Rudiger Reischuk
Abstract. The subclass of directed series-parallel graphs plays an important role in computer science. To determine whether a graph is series-parallel is a well studied problem in algorithmic graph...
Scheduling Dynamic Graphs (1999)
Andreas Jakoby, Rudiger 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...
Space Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds (1996)
Maciej Li'skiewicz, Rudiger Reischuk
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...
The Average Case Complexity of the Parallel Prefix Problem (1994)
Andreas Jakoby, Christian Schindelhauer, Rudiger Reischuk, Stephan Weis
Abstract. We analyse the average case complexity of evaluating all prefixes of an input vector over a given semigroup. As computational model circuits over the semigroup are used and a complexity...
The Average Case Complexity of the Parallel Prefix Problem (1994)
Andreas Jakoby, Christian Schindelhauer, Rudiger Reischuk, Stephan Weis
Abstract. We analyse the average case complexity of evaluating all prefixes of an input vector over a given semigroup. As computational model circuits over the semigroup are used and a complexity...