Classical vs. Quantum Read-Once Branching Programs (2008)
Abstract. A simple, explicit boolean function on 2n input bits is presented that is computable by errorfree quantum read-once branching programs of size O(n 3), while each classical randomized...
Binary Decision Diagrams (2008)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
Decision diagrams are a natural representation of finite functions. The obvious complexity measures are length and size which correspond to time and space of computations. Decision diagrams are the...
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...
On Multi-Partition Communication Complexity (2008)
Martin Sauerhoff, Georg Schnitger
Abstract. 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...
Approximability and Non-Approximability by Binary Decision Diagrams (Extended Abstract) (2007)
Beate Bollig, Martin Sauerhoff, Ingo Wegener
The usual applications of BDDs (binary decision diagrams), e. g., in verification and for CAD problems, require an exact representation of the considered boolean functions. However, if BDDs are used...
Pavol Duri S, Juraj Hromkovi C, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
Abstract. 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...
Beate Bollig, Martin Sauerhoff, Ingo Wegener
Branching programs are considered as a nonuniform model of computation in complexity theory as well as a data structure for boolean functions in several applications. In many applications (e. g.,...
Binary Decision Diagrams (2007)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
Decision diagrams are a natural representation of finite functions. The obvious complexity measures are length and size which correspond to time and space of computations. Decision diagrams are the...
Quantum vs. Classical Read-Once Branching Programs (2006)
A simple, explicit boolean function on 2n input bits is presented that is computable by errorfree quantum read-once branching programs of size O(n^3), while each classical randomized read-once...
Quantum vs. Classical Read-once Branching Programs (2005)
The paper presents the first nontrivial upper and lower bounds for (non-oblivious) quantum read-once branching programs. It is shown that the computational power of quantum and classical read-once...
On Multi-Partition Communication Complexity (2001)
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.
On multipartition communication complexity (2001)
Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
Abstract. 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...
On multi-partition communication complexity (2001)
Pavol Duris, Juraj Hromkovič, 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...
An Improved Hierarchy Result for Partitioned BDDs (2000)
Martin Sauerhoff Fb, 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...
Approximation of Boolean Functions by Combinatorial Rectangles (2000)
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...
An Improved Hierarchy Result for Partitioned BDDs (2000)
One of the great challenges of complexity theory is the problem to analyze the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. This problem could be...
Relating branching program size and formula size over the full binary basis (1999)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
Abstract. Circuit size, branching program size, and formula size of Boolean functions, denoted by C(f), BP(f), and L(f), are the most important complexity measures for Boolean functions. Often also...
On the size of randomized OBDDs and read-once branching programs for k-stable functions (1999)
Abstract. In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is...
On the size of randomized OBDDs and read-once branching programs for k-stable functions (1999)
Abstract. In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is...
Relating branching program size and formula size over the full binary basis (1999)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
Circuit size, branching program size, and formula size of Boolean functions, denoted by C(f), BP (f), and L(f), are the most important complexity measures for Boolean functions. Often also the...
. It is well-known that an arbitrary nondeterministic Turing machine can be simulated with polynomial overhead by a so-called guess-and-verify machine. It is an open question whether an analogous...
Complexity Theoretical Results for Randomized Branching Programs (1999)
Doktors Der Naturwissenschaften, Martin Sauerhoff, Gutachter Prof, Dr. Ingo Wegener, Prof Dr, ...
This work is settled in the area of complexity theory for restricted variants of branching programs. Today, branching programs can be considered one of the standard nonuniform models of computation....
Optimal Ordered Binary Decision Diagrams for Read-Once Formulas (1999)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
In many applications like verification or combinatorial optimization, OBDDs (ordered binary decision diagrams) are used as a representation or data structure for Boolean functions. Efficient...
On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions (1999)
In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described. This...
On The Complexity Of The Hidden Weighted Bit Function For Various BDD Models (1998)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verication, timing...
Hierarchy Theorems For kOBDDs AND kIBDDs (1998)
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...
A Lower Bound for Randomized Read-k-Times Branching Programs (1997)
In this paper, we are concerned with randomized OBDDs and randomized read-ktimes branching programs. We present an example of a Boolean function which has polynomial size randomized OBDDs with small,...
The complexity of the inclusion operation on OFDDs (1997)
Rolf Drechsler, Martin Sauerhoff, Detlef Sieling
Ordered Functional Decision Diagrams (OFDDs) are a data structure for representation and manipulation of Boolean functions. A polynomial time algorithm for the test whether f g for functions f and g...
On Nondeterminism versus Randomness for Read-Once Branching Programs (1997)
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...
Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract) (1997)
) Martin Sauerhoff ? Fachbereich Informatik, Universitat Dortmund, 44221 Dortmund, Germany e-Mail: sauerhoff@cs.uni-dortmund.de Abstract. Randomized branching programs are a probabilistic model of...
On Nondeterminism Versus Randomness for ReadOnce Branching Programs, ECCC (1997)
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...
Optimal Ordered Binary Decision Diagrams for Fanout-Free Circuits (1996)
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
In this paper, the OBDD variable ordering problem for functions representable by general fanout-free circuits which may contain EXOR-gates is investigated. It is proved that some depth first...
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits (1996)
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...
On The Complexity Of Minimizing The OBDD Size For Incompletely Specified Functions (1996)
Martin Sauerhoff, Ingo Wegener
The problem to construct an OBDD cover of minimal size for an incompletely specified Boolean function arises in several applications in the CAD domain, e. g. the verification of sequential machines...
Complexity Theoretical Aspects of OFDDs (1996)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
We extend the list of complexity results for OFDDs on problems arising in practical applications. We show that it is NP-hard to decide whether a function represented by some OFDD can be represented...
On The Complexity Of Minimizing The OBDD Size For Incompletely Specified Functions (1996)
Martin Sauerhoff, Ingo Wegener
The problem of constructing an OBDD cover of minimal size for an incompletely specified Boolean function arises in several applications in the CAD domain, e. g. the verification of sequential...
Complexity Theoretical Aspects of OFDDs (1996)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
Experimental results have shown that OFDDs (ordered functional decision diagrams) are a representation of Boolean functions which are sometimes superior to OBDDs (orered binary decision diagrams)....
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits (1996)
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...
On The Power Of Different Types Of Restricted Branching Programs (1994)
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...