All reports by Author Martin Sauerhoff:

__
TR01-066
| 28th September 2001
__

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger#### On Multipartition Communication Complexity

__
TR00-058
| 1st August 2000
__

Martin Sauerhoff#### Approximation of Boolean Functions by Combinatorial Rectangles

__
TR00-057
| 25th July 2000
__

Martin Sauerhoff#### An Improved Hierarchy Result for Partitioned BDDs

__
TR98-018
| 27th March 1998
__

Martin Sauerhoff#### Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1

__
TR97-030
| 25th August 1997
__

Martin Sauerhoff#### On Nondeterminism versus Randomness for Read-Once Branching Programs

__
TR97-019
| 5th May 1997
__

Martin Sauerhoff#### A Lower Bound for Randomized Read-k-Times Branching Programs

__
TR96-022
| 15th March 1996
__

Martin Sauerhoff, Ingo Wegener, Ralph Werchner#### Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

__
TR94-026
| 12th December 1994
__

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener#### On the Power of Different Types of Restricted Branching Programs

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Martin Sauerhoff

This paper deals with the number of monochromatic combinatorial

rectangles required to approximate a Boolean function on a constant

fraction of all inputs, where each rectangle may be defined with

respect to its own partition of the input variables. The main result

of the paper is that the number of ...
more >>>

Martin Sauerhoff

One of the great challenges of complexity theory is the problem of

analyzing the dependence of the complexity of Boolean functions on the

resources nondeterminism and randomness. So far, this problem could be

solved only for very few models of computation. For so-called

partitioned binary decision diagrams, which are a ...
more >>>

Martin Sauerhoff

We extend the tools for proving lower bounds for randomized branching

programs by presenting a new technique for the read-once case which is

applicable to a large class of functions. This technique fills the gap

between simple methods only applicable for OBDDs and the well-known

"rectangle technique" of Borodin, Razborov ...
more >>>

Martin Sauerhoff

Randomized branching programs are a probabilistic model of computation

defined in analogy to the well-known probabilistic Turing machines.

In this paper, we present complexity theoretic results for randomized

read-once branching programs.

Our main result shows that nondeterminism can be more powerful than

randomness for read-once branching programs. We present a ...
more >>>

Martin Sauerhoff

In this paper, we are concerned with randomized OBDDs and randomized

read-k-times branching programs. We present an example of a Boolean

function which has polynomial size randomized OBDDs with small,

one-sided error, but only non-deterministic read-once branching

programs of exponential size. Furthermore, we discuss a lower bound

technique for randomized ...
more >>>

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Many Boolean functions have short representations by OBDDs (ordered

binary decision diagrams) if appropriate variable orderings are used.

For tree-like circuits, which may contain EXOR-gates, it is proved

that some depth first traversal leads to an optimal variable ordering.

Moreover, an optimal variable ordering and the resulting OBDD

can ...
more >>>

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Almost the same types of restricted branching programs (or

binary decision diagrams BDDs) are considered in complexity

theory and in applications like hardware verification. These

models are read-once branching programs (free BDDs) and certain

types of oblivious branching programs (ordered and indexed BDDs

with k layers). The complexity of ...
more >>>